| 2 | ll sp[N]; |
| 3 | unordered_map<ll,ll> mem; |
| 4 | ll sumphi(ll n) { |
| 5 | if (n < N) return sp[n]; |
| 6 | if (mem.find(n) != mem.end()) return mem[n]; |
| 7 | ll ans = 0, done = 1; |
| 8 | for (ll i = 2; i*i <= n; i++) ans += sumphi(n/i), done = i; |
| 9 | for (ll i = 1; i*i <= n; i++) |
| 10 | ans += sp[i] * (n/i - max(done, n/(i+1))); |
| 11 | return mem[n] = n*(n+1)/2 - ans; } |
| 12 | void sieve() { |
| 13 | for (int i = 1; i < N; i++) sp[i] = i; |
| 14 | for (int i = 2; i < N; i++) { |