CAARRAY-Editorial

editorial
, , ,
22

You can find number of elements of A wich are divisible by i. Say mult[i] elements of A are divisible by i.

Now suppose dp[i] gives number of subsets of length greater than 1.

Now it’s easy to see that dp[i]=2^{mult[i]} - mult[i]-1 - \sum_{j=2}^{\frac{N}{i}} dp[i \cdot j].

So you can start from i=N, and move till i=1.

Atlast you just need to check that dp[i] > 0 for all i. Now value of dp[i] can be quite large, so I used hashing wrt two modulos.

23

I assume you made a typo and dp[i] is # of subsets whose gcd = i. The last term (summation) doesn’t look correct. I think you mixed up a[i] and i at some point. Specifically, gcd of a subset can go as high as gcd of any pair of a[j]'s that are multiples of i, so summation should go much higher than n. Given the range of a[i]'s, you would need to iterate from 10^18 down to 0.