Hi, I have a small problem that has been bothering me for a while.
Heres the problem: You're given an array which contains N integers (N <=2*1e5). Your task is to print out the sum of GCD of all 2^n-1 (pow(2,n)-1 for clear statement) subsequence. The definition of an subsquence is a set of index i1, i2, i3, ..., ik that i1<i2<i3<...<ik. You have to moduluo the answer by 1e9+7 otherwise is gonna be overflowed, also a[i] <=1e6 and N <=2*1e5.
A sample test case is:
input: 3 1 2 3
output: 10
input: 5 3 6 9 5 10 output: 72








the output of the first example seems off: gcd(3) + gcd(1) + gcd(2) + gcd(3) + gcd(3, 1) + gcd(3, 2) + gcd(3, 3) + gcd(1, 2) + gcd(1, 3) + gcd(2, 3) + gcd(3, 1, 2) + gcd(3, 1, 3) + gcd(3, 2, 3) + gcd(1, 2, 3) + gcd(3, 1, 2, 3) = 3 + 1 + 2 + 3 + 1 + 1 + 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 22
It seems to me that $$$3\ 1\ 2\ 3$$$ stands for $$$n=3$$$ and $$$a=[1,2,3]$$$
my bad, I didn't understand, it is indeed 10
Let $$$dp_i$$$ be the number of subsequences with gcd divisible by $$$i$$$. Let $$$div_i$$$ be the number of elements in array divisible by $$$i$$$. Now notice that $$$div_i = \sum_{x \gt 0}^{\lfloor\frac{10^6}{i}\rfloor}{occ_{i \cdot x}}$$$ where $$$occ_i$$$ is the number of occurences of $$$i$$$. This array can be computed naively in $$$\mathcal{O}(n \log n)$$$. Then it's easy to see that $$$dp_i = 2^{div_i} - 1$$$. Notice that the number of subsequences with gcd $$$i$$$ was added to all the divisors of $$$i$$$. From this we can come up with such algorithm: iterate from $$$10^6$$$ to $$$1$$$ and for each $$$i$$$ subtract $$$\sum_{x \gt 1}^{\lfloor\frac{10^6}{i}\rfloor}{dp_{i \cdot x}}$$$ from $$$dp_i$$$. Now $$$dp_i$$$ means the number of subsequences with gcd = i. The answer is $$$\sum_{i = 1}^{10^6}{dp_i \cdot i}$$$.
I see our solutions are the same (but you posted 5 mins before because I type too slowly lol), idt there's a better complexity one.
In this solution we will iterate over every number from 10^6 to 1 and calculate by how much it contributes to the sum (that is the number of subsequences such that it is equal to their gcd). Note that we're iterating from the biggest possible gcd (10^6) to the lowest (1) this is important.
Let's keep track of an array c[10^6] which stores the contribution of each number so far, let's also use an array occ[10^6] which stores the number of occurrences of each element in the given array. Let x be the number our iteration is currently on.
We want to calculate the number of subsequences such that it's their gcd, this is the same thing as the number of subsequences such that x divides all of the elements minus the contribution of all the multiples of x. we will calculate both of them in a single iteration. So let's iterate over all the multiples of x, we can easily compute the number of multiples of x in the given array (let's call this number M) and the contribution of all multiples of x (let's call it D), the number of subsequences such that their gcd is equal to x is c[x] = 2^M - 1 - D. and we should add x * c[x] to the answer. Complexity is O(A*log(N)) where A is the maximum value in the array (10^6).
Here's my code:
sadly, your code is only passed 15/50 test cases. Anyway, thank u so much for the idea, let me see if I could fix this
I’m pretty sure the issue is overflow. Just change x*c[x] to 1LL*x*c[x]?
Thank you I didn't see it