genkaim

定義#

歐拉函數是由$n$指向 小於等於$n$且與$n$互質的正整數個數 的函數，用$phi(n)$表示。

範例

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);
    }
  }
}