### puneet_tyagi's blog

By puneet_tyagi, 6 months ago, Hey Codeforces! This was a question asked in Media.net online assessment, help in solving the question is appreciated.

Problem: We are familiar with primes. Here we define omega prime.

A number X is an omega prime such that any perfect square of Y (Y > 1) doesn't divide X, such as 2 and 6 are omega primes while 12 is not an omega prime since it can be divided by 2*2. Now we are given an array A of integers, we need to find out the total number of subsets such that the product of elements of the subset is omega prime. The answer can be huge, hence output modulo 1000000007.

1 <= A.size() <= 2 * (10^4)

1 <= A[i] <= 30 Comments (6)
 » Note: the problem's definition of "omega primes" is formally called "Square-free integers".
 » 6 months ago, # | ← Rev. 2 →   Lets exclude 1 for now. Now, we have 18 such "omega prime" numbers. now we see which subsets can form omega prime numbers, which can be done in 2^18. Now for each valid subset we just have we just multiply their counts (as we can only include one of each type). And to include 1, in each valid subset we just multiply it by 2^(count of 1)
•  » » I got it, thanks a lot.