Подсчет подмножеств, произведение которых не делится на полный квадрат
Учитывая массив arr[] (где arr[i] лежит в диапазоне [2, 30] ) размера N , задача состоит в том, чтобы найти количество подмножеств, таких что произведение элементов не делится ни на какое число с совершенным квадратом .
Примеры:
Input: arr[] = {2, 4, 3}
Output : 3
Explanation:
Subset1 – {2}
Subset2 – {3}
Subset3 – {2, 3} 6 is not divisible by any perfect square number greater than 1Input: arr[] = { 2, 2, 2 }
Output: 3
Explanation:
{2} subset contains an element at index 0
{2} subset contains an element at index 1
{2} subset contains an element at index 2
Подход: Задача может быть решена на основе следующей идеи:
Suppose the product is X. X can be written as X = p1e1 * p2e2 * p3e3 * . . . where pi is a prime number and ei is the exponent for the prime number pi. So we can conclude that all the prime numbers should have exponent 1. Otherwise, X would be divisible by a perfect square.
As the constraint for arr[i] is 30, there are only 10 primes under that {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}. So total 1024 numbers are possible. The task is to find the subsets with product being any of these numbers.
Следуйте шагам, указанным ниже, чтобы реализовать идею:
- Создать карту и сохранить частоту всех элементов массива.
- Создайте массив для хранения всех простых чисел меньше 30.
- Создайте фиктивный массив (скажем, temp[] ) и сохраните числа, которые можно составить, используя простые числа меньше 30.
- Затем инициализируйте переменную и сохраните результат.
- Запустите цикл и выполните итерацию по массиву temp.
- Начните еще один цикл от j = 1 до j*j < i, чтобы подсчитать идеальные квадраты.
- Внутри этого цикла подсчитайте количество подмножеств, в которых произведение равно i , и увеличьте ответ.
- Начните еще один цикл от j = 1 до j*j < i, чтобы подсчитать идеальные квадраты.
- Верните ответ по модулю.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(1024 * sqrt(X)) где X - наибольшее число в temp
Вспомогательное пространство: O(2 ·10 )
Статьи по Теме:
- Введение в массивы - учебные пособия по структурам данных и алгоритмам