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 sieve

and you can generate all divisors of a number in O(number of divisors) using the information generated by sieve

then 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

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.

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.

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