PROBLEM LINK:Author: Pavel Sheftelevich DIFFICULTY:HARD PREREQUISITES:Math, Numbertheory PROBLEM:You are given integer N and integer D. Your task is to compute the number of unordered pairs of numbers $\{A, B\}$ such that $1 \leq A, B \leq N$ and $\gcd(A, B) = D$. QUICK EXPLANATION:First notice that the number of pairs which we are looking for equals the number of coprime number nongreater than $N \mathbin{/} D$. Then use Eulertotient function to compute the number of coprime numbers notgreater than $N \mathbin{/} D$. In order to pass all testcase, use precomputation of sums of Eulertotient function for some intervals to speed up the real time computation. EXPLANATION:The crucial observation here is that the number of unordered pairs of number $\{A, B\}$ not greater than $N$, for which $\gcd(A, B) = D$ equals the number of coprime numbers not greater than $N \mathbin{/} D$. This is true, because if you multiply these coprime numbers by $D$, then their $\gcd$ equals $D$, since they do not share any common prime factors other that prime factors of $D$. We just reduced our problem to finding the number of coprime number non greater than some integer $N$. The most straightforward method to do that is to iterate over all possible pairs of number and check if their $\gcd$ equals $1$ using Euclid algorithm. This results in algorithm which has $O(N^2 \cdot \log(N))$ complexity. This allows us to solve the first subtasks, but is a way too slow for higher constraints. The faster solution uses Eulertotient function which is a very famous function denoted by $\phi(N)$. The value of $\phi(N)$ is the number of positive integers not greater than $N$ which are coprime with $n$. It can be computed using factorization. So the number of coprime number smaller than $N$ equals the sum of $\phi(i)$ for all $i \leq N$. For more details, I encourage you to read this great topcoder tutorial on prime numbers, factorization and Euler function. But since we have to compute $\phi(i)$ for all numbers from $1$ to $N$, this will time out, because $N$ can be at most $5 * 10^8$. In order to speed up our solution, we can precompute values of sums of $\phi$ of integers not greater than $K, 2 K, 3K, \dots, N  K$ for reasonable chosen $K$. Author of the problem decides to choose $K$ to be $250000$. This allows us to compute $\phi$ for at most $K$ different values and uses the precomputed sum of $\phi$ for smaller values. The time complexity here depends on $K$ and equals $O(K \cdot \log(N) + N \cdot \log(\log(N)))$, where the first summand is taken from computing $\phi$ for at most $K$ values, and the second is taken from computing prime numbers using in factorization  we can use the sieve in order to do that. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 26 Jul '15, 14:27

Basically this question requires you to efficiently compute the sum of etf form 1 to n/d For doing same an awesome post by a user mclo is here ! Implementation of above > Solution link answered 26 Jul '15, 14:54
How can your code pass in given time if n=5*10^8 and d = 2 as in you code this for loop :"for(val=n/d; val>0; val){}" iterate n/d times?
(26 Jul '15, 16:08)
For that function d isn't that one given in problem ... For the loop which you are talking about d has reached around sqrt(n) at that time ! So you need to iterate sqrt(n) times !
(26 Jul '15, 17:19)
Can you please explain your code a little bit? I understood the part where you found the ETF function and their summation. This is enough for two subtasks. But how did you find the results when the number is more than MAX? Please give some hints.
(27 Jul '15, 20:05)
3
I make use of the recursion shown in the picture ! (WARNING: d in that function isn't that one given in problem) Idea is (n/d) value will be unique for d less than or equal to sqrt(n) .. After that (n/d) will assume only sqrt(n) different values .. that is (n/d) would repeat for ranges of d ! So instead of iterating d from sqrt(n) to n directly .. you can just iterate (n/d) itself and corresponding to that obtain the range of d ! Simmilar problem with this idea: 1. spoj.com/problems/AFS2 2. https://projecteuler.net/problem=401
(28 Jul '15, 01:07)
nice implementation. easy to understand as well.
(22 Jul '16, 21:14)

@ayushtomar @ironmandhruv : Apologies, the solution links have been fixed. answered 26 Jul '15, 15:06

Basically , what i got is we have to find summation of ETF from 1 to p where p is n/d . But the actual problem was how to do that summation . Thanks adkroxx for the solution implementation . answered 26 Jul '15, 15:09

Neither author nor tester's solution are available answered 26 Jul '15, 14:41

@adkroxx where did you find this nice piece of theory? answered 26 Jul '15, 15:57
Problems on projecteuler.net have thread forum associated with them and also overview for many of them once you solve a problem .. Above theory is one of them :)
(26 Jul '15, 20:36)

@adkroxx ,i didnt get this,,,if n(n+1)/2= {1<=a<=b<=n}=\sum(phi(n/d)) ,then how required_ans=n(n+1)/2\sum(phi(n/d)),,,(sorry i didnt know how to use latex here) answered 26 Jul '15, 20:37
(n*(n+1))/2 = sum(sp(n/d)) (d=1 to n) i.e. (n*(n+1))/2 = sp(n/1) + sum(sp(n/d)) (d=2 to n) rearrange to get answer .. here sp is summation of phi function !
(26 Jul '15, 20:42)
got it thnx,so silly of me
(26 Jul '15, 23:56)

Nice problem. Learned a very good thing. Thanks. answered 27 Jul '15, 10:24

I am not able to understand why there is a term of k.log(n) in the time complexity. According to author and tester solutions, these k values are calculated from a different code. Also how can we compute the sum of all k values up to N in time K.log(n).