Блог пользователя wakaranai

Counting the number of subsets of an array whose GCD is 1?
Автор wakaranai, история, 2 года назад, По-английски

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?

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
2 года назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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 :(

→ Ответить
»
2 года назад, # |
← Rev. 5   Проголосовать: нравится +8 Проголосовать: не нравится

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)$$$

→ Ответить