欧拉函数、欧拉筛

欧拉函数 | 欧拉筛#

简述#

欧拉函数 $\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$ 可以写成 $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; }
        }
    }
}