欧拉函数

欧拉函数（Euler’s totient function），表示的是小于等于 n 和 n 互质的数的个数。

公式

设 ，其中 是质数，有

证明

设 是 的质因子， 中 的倍数有 共 个。

同理，若 也是 的质因子，则 中 的倍数有 个。

如果把 和 的倍数去掉， 的倍数就被算了两次，应再加回 。

对于有两个质因子的正整数

同理，对于任意正整数

性质

1. 当 为质数时，。
2. 对于任意 的整数， 中与 互质的数的和为
3. 欧拉函数是积性函数，即若 与 互质，则 。

证明

对于性质一，因为 为质数，所以 与 都互质。

对于性质二，因为 所以与 互质的数成对出现，每对数的平均值为 ，共有 个数。

对于性质三，可以通过计算公式看出。

计算

对于单个数，根据计算公式计算即可。

int GetPhi(int x) {
  int res = x;
  for (int i = 2; i <= std::sqrt(x); i++) {
    if (x % i == 0) {  // i 是 x 的因数
      res = res / i * (i - 1);
      while (x % i == 0) x /= i;
    }
  }
  if (x > 1)  // n 是质数
    res = res / x * (x - 1);
}

对于求 的数的欧拉函数值，因为欧拉函数为积性函数，所以使用线性筛可以在 解决问题。

int prime[N], phi[N];
bool v[N];

int GetPhi(int n) {
  memset(v, 0, sizeof(v));
  int cnt = 0;
  phi[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (!v[i])  // i 为质数
      prime[++cnt] = i, phi[i] = i - 1;
    for (int j = 1; j <= cnt && prime[j] * i <= n; j++) {
      int now = prime[j] * i;
      v[now] = true;  // now 为合数
      if (i % prime[j] == 0) {
        phi[now] = phi[i] * prime[j];
        break;
      }
      phi[now] = phi[i] * (prime[j] - 1);
    }
  }
}