I have been trying to solve this problem for past 2 days, but I havent come up with a formal solution.

I have tried to change the order of sums and grouping by gcd but couldnt get any further than getting a bound on distinct values of gcd .

Can someone please help?

Source: PE 530

Some hints (actually, I didn't solve problem but I'm sure this things will help for solving):

Lemma.Letdbe divisor ofnandGCD(n,x) =d(herexis some number). Thenx=d*kfor some positive integerk. Then .Theorem.Let . Then . Here φ(n) is Euler function.Bonus :)You can calculate φ(i) inO(nlogn) with Euler sieve.Euler sieve codeI appreciate your reply, but I already know everything you mentioned and have tried on those terms.

And whats with the downvoting? Did I do something wrong to ask a doubt or is it glaringly easy that I have asked?

here is how I solved it :

let x = gcd(d,) ... this means the x|d and x| which means that

x^{2}|kthat means that you can compute the answer as the contribution of every x where x^2 <= 10^15for any x with

x^{2}≤ 10^{15}notice that for any k withx^{2}|k... let d be any divisor such that x|d and x| then x will be counted times where σ_{0}(n) is the number of divisor of n ,but there is a catch .. what if there is ay=q*xwithy^{2}|kthe way around it is to subtract y's contribution leading to a formula :

but now you ask how to compute ,well there is a way to compute in O() actually it works for any power of the divisors in the same time which is O(* (time to compute )) ,I explained it briefly on the case of σ

_{1}here ,the famous mathematician Terence Tao explained it here and you can test your understanding of it on this problemso the answer is where and

N= 10^{15}the time to compute all σ

_{0}isthe time to compute the contribution after previous step is then the total time is

Thanks you very much for your detailed explanation, I get the idea. And + 1 for reference to extra problems :)