The following problems involve a sum of gcd. And this particular type of ideas are needed in some other problems too.

GCD

GCD Extreme I

GCD Extreme II

Best Friend

The first problem can solved by brute-force. But the latter problems will get you a TLE. So, we need to be tricky here. Let's assume we already know what Euler's Totient Function is and how to compute it efficiently. First we analyze the last problem. We need a lemma.

Lemma If d is a divisor of n, then there are Phi(n/d) numbers i <= n for which gcd(i,n)=d

Proof: We can see an example which certainly generalizes. Say, n=12 and we want to compute the number of numbers i <= 12 so that gcd(i,12)=3. Let's do it by hand first. These i are 3,9. Now, we compute it by logic.

First off, any such i must be divisible by 3. So, assume i=3j. Then gcd(12,3j)=3*gcd(j,4). Now, if gcd(4,j) is greater than 1, then our desired gcd will be greater than 3. Therefore, we must have gcd(4,j)=1. How many such j are there? Phi(4). So, the number of such i is the number of such j, i.e. Phi(4)=Phi(12/3). You can check it with other examples. And generally, it follows that for a divisor d, we would have such Phi(n/d) numbers.

According to the problem 4, we need to find the number of such numbers i <= n such that gcd(i,n) <= x. Again, gcd(i,n) is always a divisor of n. So, the divisors which are less than x will come in this gcd. We can write this as a sum of Phi(n/d) where d are divisors of n less than x. For this particular problem, we need to store the values of Phi(n/d) and their cumulative sum, to get them within O(1) query. Otherwise the program will be timed out. Also to find the greatest divisor of n less than or equal to x, a linear search won't be enough. You will need binary search.

The first 3 problems are the same, only the variation is in the limit. We solve the 3rd without loss of generality.

We are asked to find

We denote the sum by G(n) for a particular n for convenience. First, the tricky part is to notice that,

G(n)=G(n-1)+S(n)

where S(n) is the summation of gcd(i,n) where i runs from 1 to n-1. So, if we can find S(n) fast enough, we can solve the problem taking cumulative sum.

Next, we apply the same lemma as before. For a particular i, how many times does gcd(i,n) occurs? Since gcd(i,n)=d is a divisor of n, then d would occur Phi(n/d) times in the sum S(n). Thus, S(n) is the summation d*Phi(n/d) where d is any divisor of n. In this problem, you need to store the values of Phi in an array while running the Sieve.

By the way, we can prove easily that, sum of Phi(d) = n where d is a divisor of n. So, if x >= n, in the problem Best Friend, the answer would be just "n". O(1) solution!! To sense this, try according to the previous lemma's proof.

Try them. Happy coding!!