### -synx-'s blog

By -synx-, history, 4 years ago,

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 .
 » 4 years ago, # |   +2 Some hints (actually, I didn't solve problem but I'm sure this things will help for solving):Lemma. Let d be divisor of n and GCD(n, x) = d (here x is some number). Then x = d * k for some positive integer k. Then .Theorem. Let . Then . Here φ(n) is Euler function.Bonus :) You can calculate φ(i) in O(nlogn) with Euler sieve. Euler sieve codevoid euler() { for (int i = 2; i < MAX; i++) phi[i] = i; for (int i = 2; i < MAX; i += 2) phi[i] /= 2; for (int i = 3; i < MAX; i += 2) if (phi[i] == i) for (int j = i; j < MAX; j += i) phi[j] -= phi[j] / i; }