Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

欧拉函数 | 欧拉筛


简述

欧拉函数ϕi\phi_i(phii)(phi_i)表示<=i<=i并且与ii互质的数的个数。非完全积性函数。

欧拉筛是一种线性筛。时间复杂度O(UpperLimit)O(UpperLimit)。可以用来线性求积性函数。


原理

欧拉筛

欧拉筛抓取当前的素数ii与以前的素数Primes1PrimescntPrimes_1 \sim Primes_{cnt}相乘,将它们筛除。欧拉筛保证每个合数都是由其最小的质因子筛除。

其核心代码为if(i % Primes[j] == 0) break;,该句保证了欧拉筛的时间复杂度为线性。

证明:当imodPrimesj==0i\mod Primes_j == 0时,有两种可能:

  • 当$ i 是一个素数。此时说明已经抓取到了iPrimes_j == i),筛去了i2$。显然地,对于素数$i$,$i2最小的质因子是i$。
  • ii是一个合数。此时说明PrimesjPrimes_jii最小的质因子。那么iPrimesji * Primes_j的质因子即为PrimesjPrimes_jii的质因子。显然地,Primesj<iPrimes_j < i,那么PrimesjPrimes_j到目前为止是iPrimesji * Primes_j的最小质因子。但是$ Primes 数组为单调递增,之后筛的每一个iPrimes_{j’}的最小质因子已经不是Primes_{j’},而是前面的Primes_j(因为前面i \mod Primes_j == 0,那么Primes_ji的最小质因子,也是iPrimes_j$的最小质因子),那么就不能保证每个合数都是由它的最小质因子筛除的了。所以Break

另外,UpperLimitUpperLimit以内的每个合数都会被筛到。显然地,UpperLimitUpperLimit以内的每个数都拥有一个UpperLimitUpperLimit以内的质因子。


欧拉函数

ϕi\phi_i的通用表达式:ϕi=ij=1cnti(11pj)\phi_i = i * \prod_{j=1}^{cnt_i}(1-\frac{1}{p_j} ) ,使用容斥原理:

  • ii分解质因数,得到i=j=1cntpieii=\prod_{j=1}^{cnt}p_i^{e_i}ppii的质因子。那么<i<ipjp_j的任意倍数都不与ii互质。这些数的个数为$ \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有一些特别的性质。考虑ϕi\phi_i

  • 显然地,当ii是素数,那么ϕi=i1\phi_i=i-1

  • ii可以被写成pkp^k的形式,其中pp是一个素数,那么ϕi=pkpk1\phi_i = p^k - p^{k-1}

    ? 证明:考虑pkp^kϕpk\phi_{p^k} 中的数必须满足一个要求,即不含有因子pp。直接算不好算,考虑倒着算。pkp^k内含有因子pp的数为$ p,2p,3p,4p, \ldots,pp,(p+1)*p,\ldots,(p{k-1}-1)*p,p{k-1}*p,共p^{k-1}$个。

  • ii可以写成mnm*n的形式,其中m,nm,n互质,那么ϕi=ϕmϕn\phi_i = \phi_{m}*\phi_{n}。即欧拉函数的部分积性。

    ? 证明:mmnn互质,说明mmnn没有相同的质因子。那么他们的唯一分解式是完全不同的。即m=j=1cntmpjejm = \prod_{j=1}^{cnt_m}p_j^{e_j}n=j=1cntnpjejn=\prod_{j=1}^{cnt_n}p_j^{e_j}。那么ϕm=mj=1cntm(11pj)\phi_m = m*\prod_{j=1}^{cnt_m}(1-\frac{1}{p_j})ϕn=nj=1cntn(11pj)\phi_n = n*\prod_{j=1}^{cnt_n}(1-\frac{1}{p_j})。因为唯一分解式完全不同,那么很显然ϕmn=ϕmϕn\phi_{m*n} = \phi_m*\phi_n

根据ϕ\phi的定义和ϕ\phi的性质,考虑ϕi\phi_i的递推求法:

  • ii是素数,ϕi=i1\phi_i=i-1

  • ii不是素数:

    i=xpi = x * p,其中pp是素数。

    • ppxx的因数,那么此时ϕi=pϕx\phi_i=p*\phi_x

      ? 证明:这个证明稍微麻烦一点。设ϕx\phi_x里的任一元素为aa。首先摆个事实,对接下来证明有用:

      ? · 当aaxx互质,那么aa一定与xpx*p互质(pp是前文中提到的素数)。

      ? 接下来,我们还要证明当aaxx互质,a+xa+x也与xx互质。显然地,a,xa,x互质gcd(a,x)=1\Leftrightarrow gcd(a,x) =1。所以我们要证的就是gcd(a+x,x)=1gcd(a+x,x)=1。可以采用反证法:(当然这就是个更相减损术)

      ? 假设gcd(a+x,x)=bgcd(a+x,x)=b(其中b1b \neq 1)。再设a+x=k1b,x=k2ba+x = k_1*b,x=k_2*b。那么a=(k1k2)ba=(k_1-k_2)*b。显然地,gcd((k1k2)b,k2b)=bgcd((k_1-k_2)*b,k_2*b) = b,那么gcd(a,x)>=bgcd(a,x)>=b

      ? 那么证得这个有什么作用呢?我们想证明ϕi=pϕx\phi_i=p*\phi_x。有了上面的结论,那么我们对于每一个在ϕx\phi_x集合里的元素aa都已知它与ii互质。因为i=xpi=x*p,那么在xx之内的a,a+x,a+2x,,a+(p1)xa,a+x,a+2*x,\ldots,a+(p-1)*x都与ii互质。这样的aa共有ϕx\phi_x个。每个aa可以扩展成pp个与ii互质的数。此时ϕi=pϕx\phi_i=p*\phi_x得证。

    • pp不是xx的因数,那么此时ϕi=(p1)ϕx\phi_i=(p-1)*\phi_x

      ? 证明:显然此时ppxx互质,那么ϕi=ϕxϕp\phi_i = \phi_x * \phi_p,又已知ϕp=p1\phi_p = p-1,那么ϕi=(p1)ϕx\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; }
        }
    }
}

评论