puneet_tyagi's blog

By puneet_tyagi, 6 months ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Note: the problem's definition of "omega primes" is formally called "Square-free integers".

»
6 months ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

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)

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

could you provide us the link please?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    These are conducted on various platforms, there is no formal link as such.

»
6 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Any number can be expressed as product of some power of primes. Now omega prime is such a number in which the power of any prime can be atmost 1 (if it's 2 or greater, it will be divisible by the square of that prime). Now there are 10 primes in the range [1,30]. So we can solve this using bitmask dp (dp[i][mask]), where mask will denote which primes have already been taken till the ith element of the array.