定义

欧拉函数是由$$n$$指向 小于等于$$n$$且与$$n$$互质的正整数个数 的函数，用$$phi(n)$$表示。

example

phi(2) = 1，（1）
phi(3) = 2，（1，2）
phi(4) = 2，（1，3）
phi(5) = 4，（1，2，3，4）
phi(6) = 2，（1，5）

公式

结论

假设n的质因数分解为$$p_1^a \times p_2^b \times ... \times p_m^k$$（$$p_i$$是质因数），则欧拉函数可以用公式求得：
$$phi(n) = n \times (1- \cfrac{1}{p_1} ) \times (1- \cfrac{1}{p_2} ) \times ... \times (1-\cfrac{1}{p_m})$$

推导

首先一个数$$x$$与$$n$$互质，说明没有公共的质因子，即$$x$$不能有$$p_1$$、$$p_2$$、...$$p_m$$等质因子。
那么$$1...n$$中有$$p_1$$质因子的个数为$$\cfrac{n}{p_i}$$。
同样，对质因子$$p_i$$，$$1...n$$中有$$\cfrac{n}{p_i}$$个 数带$$p_i$$质因子。
显然，没有$$p_i$$的质因子的数量，就是要减去$$\cfrac{n}{p_i}$$，即$$n-sum(\cfrac{n}{p_i})$$。

加上重复减去的数，根据容斥原理就得到了：

·$$phi(n) = n - sum( \cfrac{n}{p_i} ) + sum( \cfrac{n}{p_i \times p_j} ) - ... + (-1)^m \times \cfrac{n}{p_1 \times p_2} \times ...\times p_m
=n(1- \cfrac{1}{p_1}) \times (1-\cfrac{1}{p_2})...(1-\cfrac{1}{p_m})$$

朴素算法

1

根据定义，直接枚举$$1...n$$里与$$n$$的最大公约数是1的个数。

  for(int i=1; i<=n; i++)
    ans += gcd(n, i)==1;

2

根据公式

$$phi(n) = n \times (1- \cfrac{1}{p_1} ) \times (1- \cfrac{1}{p_2} ) \times ... \times (1-\cfrac{1}{p_m})$$

循环求质因子，在过程中计算 ans=ans*(1-1/pi) ,即 ans-= ans/pi

  ans = n;
  for(int i=2; i*i<=n; i++) {
    if(n%i==0) {
      ans -= ans/i;
      while(n%i==0) n/=i;
    }
  }
  if(n>1) ans -= ans/n;

筛法解法

埃氏筛法

根据欧拉函数的定义，$$phi(x)=x \times (1- \cfrac{1}{p_i})$$

埃氏筛法的原理是用素数$$p_i$$ 筛所有的倍数$$j \times p_i$$，说明此时$$j \times p_i$$有一个质因数$$p_i$$，因此可以用上面的公式进行递推。

• 首先 phi[x] = x
• 对每个素数$$p_i$$的倍数 j , 有phi[j] *= (1-1/pi)，也即phi[j] -= phi[j]/pi
  • 如果对于某个i，其phi[i] != i，说明之前筛过，是合数

void shai(int mx) {
  for(int i=1; i<=mx; i++)
    phi[i] = i;
  for(int i=2; i<=mx; i++) {
    if(phi[i] != i) continue;
    for(int j=i; j<=mx; j+=i)
      phi[j] -= phi[j]/i;
  }
}

欧拉筛法

对于某个质数$$p_i$$，分两种情况分析：

1. 如果是x的质因子，则对$$x \times p_i$$ 来说，pi已经在欧拉函数里计算了$$(1-\cfrac{1}{p_i})$$，因此有：$$phi(x \times p_i) = phi(x) \times p_i$$
2. 如果不是x的质因子，则对$$x \times pi$$来说又多了一个质因子，有：$$phi(x \times p_i) = phi(x) \times p_i \times (1- \cfrac{1}{p_i}) = phi(x) \times (p_i - 1)$$

结合欧拉筛法，就可以求phi[x]的代码。

void shai(int mx) {
  phi[1] = 1;
  for(int i=2; i<=mx; i++) {
    if(!notPrime[i]) {
      p[++last] = i;
      phi[i] = i-1;
    }
    for(int j=1; j<=last; j++) {
      int t = i * p[j];
      if(t>=mx) break;
      notPrime[t] = true;
      if(i % p[j]==0) {
        phi[t] = phi[i] * p[j];
        break;
      } else
       phi[t]= phi[i] * (p[j]-1);
    }
  }
}