XETF - Editorial

[saurabh060792]

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Inclusion Exclusion Principle, Bernoulli number

PROBLEM:

Given n and k, find the sum of all the number to the power k which are coprime with n. That is, we have to find A₁^K + A₂^K+…+A_M^K where all A_i are coprime with n.

EXPLANATION:

In this problem, our strategy will be to first calculate sum of all the numbers to the power k from 1 to n. Then subtract all those numbers whose gcd with n is greater than 1. The first part is to calculate S_k(n) = 1^k + 2^K+…+n^K. This can be done by using the following formula

S_k(n) = \frac{1}{k+1}\sum_{i=0}^k {k+1 \choose i}B_in^{k+1-i}

where B_i is the ith Bernoulli number. For more detail, look at this problem and its editorial which discusses some more ways to compute S_k(n) with their proofs. Clearly we can compute this in \mathcal{O}(k) time if we have precomputed all the Binomial and Bernoulli’s terms.

Now the first part is complete. Moving on to the next part we have to subtract all those numbers whose gcd with n is greater than 1. For this we will first factorize n. Note that the product of first 12 primes is greater than 10¹², so number of distinct primes in the prime factorization of n will be atmost 11. After factorization, we will subtract the kth power of all those number whose gcd with n is any of those primes. To accomplish this, we will use Inclusion Exclusion principle. For example if our input is (n = 10(=2 * 5), k) we will subtract all those number to the k ^th power whose gcd with 10 is 2 that are 2^k+4^k+6^k+8^k+10^k = 2^k S_k(n/2). Same with 5, that is we have to subtract 5^k+10^k = 5^k S_k(n/5). But now we have subtracted 10 two times so we have to add 10^k = 10^k S_k(n/10).

In the general case, when the prime factors of n are P = {p₁, p₂…p_m}. Then we have to add the following quantity which is the compact form of inclusion exclusion identity to S_k(n)

\sum_{s \in P}(-1)^{|s|}P(s)^k\times S_k(n/P(s))

where P(s) is the product of all the primes in set s. Now the total number of operations will be of the order \sqrt(n) (prime fact part) + 2^{11}k (In. Ex. Part) which is small enough to pass the largest test case.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

[contesant]

We can calculate S_k(n) without Bernoulli Numbers. It is obvious that S_k(n) is a polynomial with k + 2 degree. We can use interpolation to calculate coefficients. Overall complexity would be O(k^3) if we use gauss elimination to do interpolation and O(k^2) if we use Newton’s Interpolation.