wakaranai's blog

Counting the number of subsets of an array whose GCD is 1?
By wakaranai, history, 22 months ago, In English

Problem link

Array length n <= 100

Array elements can be up to 1e9.

If the elements were ~ 2e5 it could be done by fixing the length of subsets and counting them individually with the mobius function. But I cant think of any way to optimize this approach to work for the given constraints.

Does this problem require a completely different approach/technique?

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
22 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

The possible GCDs of a subset must divide at least one of the array elements: considering only them should get AC.

→ Reply
»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

If the elements were ~ 2e5 it could be done by fixing the length of subsets and counting them individually with the mobius function. But I cant think of any way to optimize this approach to work for the given constraints.

it's not morbin time :(

→ Reply
»
22 months ago, # |
← Rev. 5   Vote: I like it +8 Vote: I do not like it

Let the array be $$$A$$$. Let $$$M = max(A[1],A[2]...A[n])$$$. There are $$$O({z}^{1/3})$$$ divisors of $$$z$$$. Every $$$gcd$$$ has to be a divisor of some $$$A[i]$$$. So, there are $$$O(N*{M}^{1/3})$$$ different values possible for $$$gcd$$$.

Let $$$dp[j]$$$ represent the number of subsets having $$$gcd = j$$$. If I'm at index $$$i$$$, update all the values of $$$dp[gcd(j,A[i])]$$$ via forward style DP. Iterate over $$$j$$$ from lower to higher value for correct order. (Take care of the case when $$$j=0$$$).

$$$dp[gcd(j,A[i])] <= (dp[gcd(j,A[i])] + dp[j]) \,\, mod \,\, ({10}^{9}+7)$$$

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

    Thanks. I'll try that

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      Note that you can still use the Mobius function (only over the values $$$j$$$) instead of DP.

      → Reply