前言

首先，根据欧拉函数的公式可以证明它是一个积性函数，于是有 $\varphi (a\ast b)=\varphi \left(a\right)\ast \varphi \left(b\right)$ϕ(a∗b)=ϕ(a)∗ϕ(b)。对于欧拉函数有个性质： $当x\mid p时，有\varphi (x\ast p)=\varphi \left(x\right)\ast p;否则\varphi (x\ast p)=\varphi \left(x\right)\ast \varphi \left(p\right)=\varphi \left(x\right)\ast (p-1)$当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
      }
    }
  }
}