欧拉函数 | 欧拉筛

简述

欧拉函数$\phi_i$$(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$可以写成$m*n$的形式，其中$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_{m*n} = \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_1*b,x=k_2*b$。那么$a=(k_1-k_2)*b$。显然地，$gcd((k_1-k_2)*b,k_2*b) = b$，那么$gcd(a,x)>=b$。

    ? 那么证得这个有什么作用呢？我们想证明$\phi_i=p*\phi_x$。有了上面的结论，那么我们对于每一个在$\phi_x$集合里的元素$a$都已知它与$i$互质。因为$i=x*p$，那么在$x$之内的$a,a+x,a+2*x,\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$就显然了。

实现

1
2
3
4
5
6
7
8
9
10

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