前言

首先，根据欧拉函数的公式可以证明它是一个积性函数，于是有 $ϕ (a * b) = ϕ (a) * ϕ (b)$ 。对于欧拉函数有个性质： $当 x ∣ p 时，有 ϕ (x * p) = ϕ (x) * p; 否则 ϕ (x * p) = ϕ (x) * ϕ (p) = ϕ (x) * (p - 1)$ 。

代码实现：

bool vis[maxn];
int prime[maxn],len;
void euler(int n) {
  int k;
  memset(vis, false, sizeof(vis));
  phi[1]=1;
  vis[1]=true;
  len = 0;
  for (int i = 2; i <= n; i++) {
    if (!vis[i]) {
      phi[i]=i-1; //i为质数，则除了自己其他数字都与其互质(gcd(k,i)=1)
      prime[++len]=i;
    }
    for (int j = 1; j <= len; j++) {
      k = i * prime[j];
      if (k > n) break;
      vis[k] = true; //筛掉
      if (i % prime[j] == 0) { //找到一个最小质因数就要剔除
        phi[k]=phi[i]*prime[j];  //if p | x : Ø(x*p) = Ø(x) * p
        break;
      } else {
        phi[k]=phi[i]*phi[prime[j]]; //积性函数的性质 phi[prime[j]] == prime[j]-1
      }
    }
  }
}