585E — Present for Vitalik the Philatelist

The problem has been prepared by gridnevvvit.

Let's calculate the number of subsets with gcd equal to 1 — value A. Let's do that using principle of inclusions-exclusions: firstly we say that all subsets is good. The total number of subsets is equal to 2n. Now let's subtract subsets with gcd divisible by 2. The number of that subsets is equal to 2cnt2 - 1 (cnti is the number of numbers that is divisable by i). Next we should subtract 2cnt3 - 1. Subsets with gcd divisible by 4 we already counted with number two. Next we should subtract 2cnt5 - 1. Now we should notice that subsets with gcd divisible by 6 we already processed twice: firstly with number 2, then with — 3, so let's add the number of these subsets 2cnt6 - 1. If we continue this process we will get, that for all numbers d we should add the value μ(d)(2cntd - 1), where μ(d) is equals to 0, if d is divisible by square of some prime, 1, if the number of primes in factorization of d is even and  - 1 in other case. So the numbers that is divisible by square of some prime we can ignore, because they have coefficient 0. To calculate values cnti we should factorize all numbers and iterate over 2k divisors with value μ(d) ≠ 0. Now it's easy to see, that the number of subsets with gcd greater than 1 equals to B = 2n - A. To solve the problem let's fix the stamp that Vitaliy will buy ai. Let's recalculate the number B for array a without element ai. To do that we should only subtract those terms that was affected by number ai. We can do that in 2k, where k is the number of primes in factorization of the number ai. It's easy to see that only the subsets with gcd greater than 1, but not divisible by any divisor of ai, should we counted in answer. To calculate number of those subsets let's again use the principle of inclusions-exclusions. For every divisor d of ai let's subtract the value μ (2cntd - 1) from B. So now we got Bi — the number of subsets with gcd greater than 1, but coprime with ai. The answer to problem is the sum over all Bi. The maximum number of primes in factorization of number not greater than 107 is equal to 8. We can factorize all numbers from 1 to n in linear time by algorithm for finding the smallest divisors for all intergers from 1 to n, or by sieve of Eratosthenes in O(nloglogn) time.

Complexity: O(C + n2K), where , K — is the largest number of primes in factorization of ai.