歐拉函數、歐拉篩

欧拉函數 | 歐拉篩#

簡述#

歐拉函數 $\phi_i$ 表示 $<=i$ 並且與 $i$ 互質的數的個數。非完全積性函數。

歐拉篩是一種線性篩。時間複雜度 $O (UpperLimit)$。可以用來線性求積性函數。

原理#

歐拉篩#

歐拉篩抓取當前的素數 $i$ 與以前的素數 $Primes_1 \sim Primes_{cnt}$ 相乘，將它們篩除。歐拉篩保證每個合數都是由其最小的質因子篩除。

其核心代碼為if(i % Primes[j] == 0) break;，該句保證了歐拉篩的時間複雜度為線性。

證明：當 $i\mod Primes_j == 0$ 時，有兩種可能：

當 $ i $ 是一個素數。此時說明已經抓取到了 $i$（$Primes_j == i$），篩去了 $i^2$。顯然地，對於素數 $i$，$i^2$ 最小的質因子是 $i$。
當 $i$ 是一個合數。此時說明 $Primes_j$ 是 $i$ 最小的質因子。那麼 $i * Primes_j$ 的質因子即為 $Primes_j$ 和 $i$ 的質因子。顯然地，$Primes_j < i$，那麼 $Primes_j$ 到目前為止是 $i * Primes_j$ 的最小質因子。但是 $ Primes $ 數組為單調遞增，之後篩的每一個 $iPrimes_{j’}$ 的最小質因子已經不是 $Primes_{j’}$，而是前面的 $Primes_j$（因為前面 $i \mod Primes_j == 0$，那麼 $Primes_j$ 是 $i$ 的最小質因子，也是 $iPrimes_j$ 的最小質因子），那麼就不能保證每個合數都是由它的最小質因子篩除的了。所以Break。

另外，$UpperLimit$ 以內的每個合數都會被篩到。顯然地，$UpperLimit$ 以內的每個數都擁有一個 $UpperLimit$ 以內的質因子。

歐拉函數#

$\phi_i$ 的通用表達式：$\phi_i = i * \prod_{j=1}^{cnt_i}(1-\frac {1}{p_j} )$ ，使用容斥原理：

將 $i$ 分解質因數，得到 $i=\prod_{j=1}^{cnt} p_i^{e_i}$。$p$ 是 $i$ 的質因子。那麼 $<i$ 的 $p_j$ 的任意倍數都不與 $i$ 互質。這些數的個數為 $ \frac {n}{p_1} + \frac {n}{p_2} + ... \frac {n}{p_j}$。用 $n$ 減去這些數。當然會減到一些重疊起來的情況，也就是 $\frac {n}{p_1p_2}$ 之類，把它們加回來就可以了。用容斥原理化一下這個式子，得到 $\phi_i = i * \prod_{j=1}^{cnt}(1-\frac {1}{p_i} )$。

$\phi$ 有一些特別的性質。考慮 $\phi_i$：

顯然地，當 $i$ 是素數，那麼 $\phi_i=i-1$。
當 $i$ 可以被寫成 $p^k$ 的形式，其中 $p$ 是一個素數，那麼 $\phi_i = p^k - p^{k-1}$。

? 證明：考慮 $p^k$，$\phi_{p^k}$ 中的數必須滿足一個要求，即不含有因子 $p$。直接算不好算，考慮倒著算。$p^k$ 內含有因子 $p$ 的數為 $ p,2p,3p,4p, \ldots,pp,(p+1)*p,\ldots,(p^{k-1}-1)*p,p^{k-1}*p$，共 $p^{k-1}$ 個。
當 $i$ 可以寫成 $mn$ 的形式，其中 $m,n$ 互質，那麼 $\phi_i = \phi_{m}\phi_{n}$。即歐拉函數的部分積性。

? 證明：$m$ 和 $n$ 互質，說明 $m$ 與 $n$ 沒有相同的質因子。那麼他們的唯一分解式是完全不同的。即 $m = \prod_{j=1}^{cnt_m} p_j^{e_j}$，$n=\prod_{j=1}^{cnt_n} p_j^{e_j}$。那麼 $\phi_m = m*\prod_{j=1}^{cnt_m}(1-\frac {1}{p_j})$，$\phi_n = n*\prod_{j=1}^{cnt_n}(1-\frac {1}{p_j})$。因為唯一分解式完全不同，那麼很顯然 $\phi_{mn} = \phi_m\phi_n$。

根據 $\phi$ 的定義和 $\phi$ 的性質，考慮 $\phi_i$ 的遞推求法：

當 $i$ 是素數，$\phi_i=i-1$。
當 $i$ 不是素數：

設 $i = x * p$，其中 $p$ 是素數。
- 當 $p$ 是 $x$ 的因數，那麼此時 $\phi_i=p*\phi_x$。
  
  ? 證明：這個證明稍微麻煩一點。設 $\phi_x$ 裡的任一元素為 $a$。首先擺個事實，對接下來證明有用：
  
  ? ・當 $a$ 與 $x$ 互質，那麼 $a$ 一定與 $x*p$ 互質（$p$ 是前文中提到的素數）。
  
  ? 接下來，我們還要證明當 $a$ 與 $x$ 互質，$a+x$ 也與 $x$ 互質。顯然地，$a,x$ 互質 $\Leftrightarrow gcd (a,x) =1$。所以我們要證的就是 $gcd (a+x,x)=1$。可以採用反證法：（當然這就是個更相減損術）
  
  ? 假設 $gcd (a+x,x)=b$（其中 $b \neq 1$）。再設 $a+x = k_1b,x=k_2b$。那麼 $a=(k_1-k_2)*b$。顯然地，$gcd ((k_1-k_2)b,k_2b) = b$，那麼 $gcd (a,x)>=b$。
  
  ? 那麼證得這個有什麼作用呢？我們想證明 $\phi_i=p*\phi_x$。有了上面的結論，那麼我們對於每一個在 $\phi_x$ 集合裡的元素 $a$ 都已知它與 $i$ 互質。因為 $i=xp$，那麼在 $x$ 之內的 $a,a+x,a+2x,\ldots,a+(p-1)x$ 都與 $i$ 互質。這樣的 $a$ 共有 $\phi_x$ 個。每個 $a$ 可以擴展成 $p$ 個與 $i$ 互質的數。此時 $\phi_i=p\phi_x$ 得證。
- 當 $p$ 不是 $x$ 的因數，那麼此時 $\phi_i=(p-1)*\phi_x$。
  
  ? 證明：顯然此時 $p$ 與 $x$ 互質，那麼 $\phi_i = \phi_x * \phi_p$，又已知 $\phi_p = p-1$，那麼 $\phi_i=(p-1)*\phi_x$ 就顯然了。

實現#

#define rep(x,y,z) for(int x=y,I=z;x<=z;++x)
inline void Euler_Sieve(){
    rep(i,2,lim){
        if(!isprime[i]) primes[++prime]=i,phi[i]=i-1;
        for(int j=1;i*primes[j]<=lim;j++){
            phi[i*primes[j]]=phi[i]*(primes[j]-1),isprime[i*primes[j]]=true;
            if(i%primes[j]==0) { phi[i*primes[j]]=phi[i]*primes[j]; break; }
        }
    }
}