### vasandani68's blog

By vasandani68, history, 5 years ago,

Can anyone provide an explanation for this problem!! I am not able to understand the basic idea.

• 0

 » 5 years ago, # |   0 it simply search the result based on formula, for example, for n = 2the result = 2/gcd(1,2) + 2/gcd(2,2) = 2 + 1 = 3
•  » » 5 years ago, # ^ |   0 It is a naive approach and will time out.Please re-read the constraints and answer accordingly.
 » 5 years ago, # | ← Rev. 3 →   0 the sum = where d is a divisor of n and φ(x) is euler's totient function ... I don't have a proof for it ,I thought it was symmetric to which is equal to (from oeis) and it worked you can precompute φ in O(n log n) after sieveand you can generate all divisors of a number in O(number of divisors) using the information generated by sievethen you can evaluate this sum in O(number of divisors) ... I don't know if that is enough to pass the TL .. because when I solved this problem I reduced the above sum into a function of the the prime factorization and hence I could evaluate it in O(log x) for any x
 » 5 years ago, # | ← Rev. 2 →   +10 The main claim is that the sum is . This can be proved easily since there are exactly numbers with and i ≤ n. Now, since dφ (d) is a multiplicative function, so is f(n).Therefore, we can calculate f for prime powers and multiply the results to get f(n).It turns out — that . Now, preprocessing the Eratosthenes's Sieve in , we can now perform prime factorization in . It is easy to calculate f once we have the prime factorization.Therefore, the time complexity is which is good enough to pass.
 » 5 years ago, # |   0 I solved it using Pillai's Arithmetic Formula.Since gcd(i, N)1 <  = i <  = N is one of the divisors of N hence in order to compute the summation we need to find the sum . Now we need to find freq(d) .We need to find the number of i's such that gcd(i, N) = d hence i = d * j when you substitute this in the previous equation you'll get this gcd(j, N / d) = 1 . This equation means that we need to find the number of numbers less than N / d that are coprime with N / d . This is called Euler's totient function.That is how you get this equation Now coming to the codechef problem , the only change that you need to make is to substitute d with N / d . Hence the sum now becomes which same as writing Try solving now.
 » 14 months ago, # | ← Rev. 2 →   0 i implemented what Noureldin and bhishma are talking about but i am getting TLE. here is my code what i did found totient[i] — n loglogn compute ans[i] — that too is n loglogn