| 2 | int mob[L], mer[L]; |
| 3 | unordered_map<ll,ll> mem; |
| 4 | ll M(ll n) { |
| 5 | if (n < L) return mer[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 += M(n/i), done = i; |
| 9 | for (ll i = 1; i*i <= n; i++) |
| 10 | ans += mer[i] * (n/i - max(done, n/(i+1))); |
| 11 | return mem[n] = 1 - ans; } |
| 12 | void sieve() { |
| 13 | for (int i = 1; i < L; i++) mer[i] = mob[i] = 1; |
| 14 | for (int i = 2; i < L; i++) { |