| 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++) { |
| 15 | if (mer[i]) { |
| 16 | mob[i] = -1; |
| 17 | for (int j = i+i; j < L; j += i) |
| 18 | mer[j] = 0, mob[j] = (j/i)%i == 0 ? 0 : -mob[j/i]; } |
| 19 | mer[i] = mob[i] + mer[i-1]; } } |
| 20 | // vim: cc=60 ts=2 sts=2 sw=2: |