wakaranai's blog

By wakaranai, history, 11 days ago,

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

 » 11 days ago, # | ← Rev. 2 →   +1 The possible GCDs of a subset must divide at least one of the array elements: considering only them should get AC.
 » 11 days ago, # |   +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 :(
 » 11 days ago, # | ← 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)$
•  » » 11 days ago, # ^ |   0 Thanks. I'll try that
•  » » » 11 days ago, # ^ | ← Rev. 2 →   +3 Note that you can still use the Mobius function (only over the values $j$) instead of DP.
•  » » » » 11 days ago, # ^ |   0 Yep, it passed with mobius. Thanks!