Подсчет подмножеств, произведение которых не делится на полный квадрат

Опубликовано: 25 Февраля, 2023

Учитывая массив 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 1  

Input: 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 , и увеличьте ответ.
  • Верните ответ по модулю.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(1024 * sqrt(X)) где X - наибольшее число в temp
Вспомогательное пространство: O(2 ·10 )

Статьи по Теме:

  • Введение в массивы - учебные пособия по структурам данных и алгоритмам