Sum of GCDs with N — Solution & Editorial

Back to the Problem

∑ gcd(i, N) = ∑_d|N d·φ(N/d) (Pillai's function). Enumerate divisors in O(√N), each totient in O(√).

Complexity: O(√N · √)

Watch out: The answer reaches ~N log log N — 64-bit; and enumerate BOTH d and N/d per divisor pair.