Блог пользователя Erisu._.3812

Автор Erisu._.3812, история, 4 года назад, По-английски

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

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

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +18 Проголосовать: не нравится

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}$$$.

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

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.

$$$\newline$$$

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.

$$$\newline$$$

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

$$$\newline$$$

Here's my code:

Code