| 56 | bool isPrime[MAXN]; |
| 57 | int mu[MAXN]; |
| 58 | void precomp() { |
| 59 | for (int i = 1; i < MAXN; i++) { |
| 60 | isPrime[i] = true; |
| 61 | mu[i] = 1; |
| 62 | } |
| 63 | isPrime[1] = false; |
| 64 | for (int p = 2; p < MAXN; p++) { |
| 65 | if (!isPrime[p]) continue; |
| 66 | assert(mu[p] == 1); |
| 67 | mu[p] *= -1; |
| 68 | for (int j = p + p; j < MAXN; j += p) { |
| 69 | isPrime[j] = false; |
| 70 | if (j / p % p == 0) mu[j] = 0; |
| 71 | else mu[j] *= -1; |
| 72 | } |
| 73 | } |
| 74 | } |
| 75 | vi cache[MAXN]; |
| 76 | void get(int N) { // compute the cyclotomic polynomial phi_N(x) |
| 77 | if (!cache[N].empty()) return; |