欧拉函数 | 欧拉筛
简述
欧拉函数表示并且与互质的数的个数。非完全积性函数。
欧拉筛是一种线性筛。时间复杂度。可以用来线性求积性函数。
原理
欧拉筛
欧拉筛抓取当前的素数与以前的素数相乘,将它们筛除。欧拉筛保证每个合数都是由其最小的质因子筛除。
其核心代码为if(i % Primes[j] == 0) break;
,该句保证了欧拉筛的时间复杂度为线性。
证明:当时,有两种可能:
- 当$ i iPrimes_j == ii2$。显然地,对于素数$i$,$i2i$。
- 当是一个合数。此时说明是最小的质因子。那么的质因子即为和的质因子。显然地,,那么到目前为止是的最小质因子。但是$ Primes iPrimes_{j’}Primes_{j’}Primes_ji \mod Primes_j == 0Primes_jiiPrimes_j$的最小质因子),那么就不能保证每个合数都是由它的最小质因子筛除的了。所以
Break
。
另外,以内的每个合数都会被筛到。显然地,以内的每个数都拥有一个以内的质因子。
欧拉函数
的通用表达式: ,使用容斥原理:
- 将分解质因数,得到。是的质因子。那么的的任意倍数都不与互质。这些数的个数为$ \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} )$。
有一些特别的性质。考虑:
-
显然地,当是素数,那么。
-
当可以被写成的形式,其中是一个素数,那么。
? 证明:考虑, 中的数必须满足一个要求,即不含有因子。直接算不好算,考虑倒着算。内含有因子的数为$ p,2p,3p,4p, \ldots,pp,(p+1)*p,\ldots,(p{k-1}-1)*p,p{k-1}*pp^{k-1}$个。
-
当可以写成的形式,其中互质,那么。即欧拉函数的部分积性。
? 证明:和互质,说明与没有相同的质因子。那么他们的唯一分解式是完全不同的。即,。那么,。因为唯一分解式完全不同,那么很显然。
根据的定义和的性质,考虑的递推求法:
-
当是素数,。
-
当不是素数:
设,其中是素数。
-
当是的因数,那么此时。
? 证明:这个证明稍微麻烦一点。设里的任一元素为。首先摆个事实,对接下来证明有用:
? · 当与互质,那么一定与互质(是前文中提到的素数)。
? 接下来,我们还要证明当与互质,也与互质。显然地,互质。所以我们要证的就是。可以采用反证法:(当然这就是个更相减损术)
? 假设(其中)。再设。那么。显然地,,那么。
? 那么证得这个有什么作用呢?我们想证明。有了上面的结论,那么我们对于每一个在集合里的元素都已知它与互质。因为,那么在之内的都与互质。这样的共有个。每个可以扩展成个与互质的数。此时得证。
-
当不是的因数,那么此时。
? 证明:显然此时与互质,那么,又已知,那么就显然了。
-
实现
#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; }
}
}
}