Sum of all 2^n-1 subsequences

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

Let dpidpi be the number of subsequences with gcd divisible by ii. Let dividivi be the number of elements in array divisible by ii. Now notice that divi=∑⌊106i⌋x>0occi⋅xdivi=∑x>0⌊106i⌋occi⋅x where occiocci is the number of occurences of ii. This array can be computed naively in O(nlogn)O(nlog⁡n). Then it's easy to see that dpi=2divi−1dpi=2divi−1. Notice that the number of subsequences with gcd ii was added to all the divisors of ii. From this we can come up with such algorithm: iterate from 106106 to 11 and for each ii subtract ∑⌊106i⌋x>1dpi⋅x∑x>1⌊106i⌋dpi⋅x from dpidpi. Now dpidpi means the number of subsequences with gcd = i. The answer is ∑106i=1dpi⋅i∑i=1106dpi⋅i.

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: