数论函数

vector<int> minp, primes;
void sieve(int n) {
    minp.assign(n + 1, 0);
    primes.clear();

    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
        }

        for (auto p : primes) {
            if (i * p > n) {
                break;
            }
            minp[i * p] = p;
            if (p == minp[i]) {
                break;
            }
        }
    }
}

vector<int> phi;
void init_phi(int n){
  if (primes.empty()) sieve(n);
  phi.resize(n + 1);
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (i % (minp[i] * minp[i]) == 0) {
            phi[i] = phi[i / minp[i]] * minp[i];
        } else {
            phi[i] = phi[i / minp[i]] * (minp[i] - 1);
        }
    }
}

vector<int> mu;
void init_mu(int n) {
  if (primes.empty()) sieve(n);
  mu.resize(n + 1);
  mu[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (minp[i] == i) {
      mu[i] = -1;
    }
    for (int j = 0; i * primes[j] <= n; j++) {
      if (i % primes[j] == 0) {
        mu[i * primes[j]] = 0;
        break;
      }
      mu[i * primes[j]] = -mu[i];
    }
  }
}