欧拉函数
定义
对于任意的正整数 n n n,欧拉函数 ϕ ( n ) \phi(n) ϕ(n) 表示小于等于 n n n 的所有数中与 n n n 互质的数的个数。
暴力实现
那么根据定义,不难直接打出一个时间复杂度 O ( n ) O(n) O(n) 的代码,枚举所有小等于 n n n 的数字 i i i,若 gcd ( n , i ) = 1 \gcd(n,i)=1 gcd(n,i)=1 则答案 + 1 +1 +1。
代码:
#include<bits/stdc++.h>
using namespace std;
int n,ans;
int gcd(int x,int y)
{return !y?x:gcd(y,x%y);
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++)if(gcd(i,n)==1)ans++;printf("%d\n",ans);return 0;
}
很显然,这段代码效率不够高。有没有什么可以优化的地方?
欧拉函数推导
先根据定义可知以下几点:
- ϕ ( 1 ) = 1 \phi(1)=1 ϕ(1)=1
- 若 n n n 为质数,则 ϕ ( n ) = n − 1 \phi(n)=n-1 ϕ(n)=n−1,即除了 n n n 自己外全都算。
- 若 n = p k n=p^k n=pk,则 ϕ ( n ) = p k − p k − 1 \phi(n)=p^k-p^{k-1} ϕ(n)=pk−pk−1。因为只有一个数不含质数 p p p,才可以与 n n n 互质。所以就要剪掉包含质数 p p p 的那 p k − 1 p^{k-1} pk−1 个数字。而 p k − p k − 1 = p k ( 1 − 1 p ) = p k p − 1 p p^k-p^{k-1}=p^k(1-\frac{1}{p})=p^k\frac{p-1}{p} pk−pk−1=pk(1−p1)=pkpp−1。
- 若 n = a b n=ab n=ab,其中 a , b a,b a,b 互质,则 ϕ ( n ) = ϕ ( a ) × ϕ ( b ) = ( a − 1 ) × ( b − 1 ) \phi(n)=\phi(a)\times\phi(b)=(a-1)\times(b-1) ϕ(n)=ϕ(a)×ϕ(b)=(a−1)×(b−1)。反过来也一样, ϕ ( a b ) = ϕ ( a ) × ϕ ( b ) \phi(ab)=\phi(a)\times\phi(b) ϕ(ab)=ϕ(a)×ϕ(b)。
- 若 n = p 1 k 1 p 2 k 2 ⋯ p i k i ⋯ p m k m n=p_1^{k_1}p_2^{k_2}\cdots p_i^{k_i}\cdots p_m^{k_m} n=p1k1p2k2⋯piki⋯pmkm,则根据第三点,可表示为 p 1 k 1 p 1 − 1 p 1 p 2 k 2 p 2 − 1 p 2 ⋯ p m k m p m − 1 p m p_1^{k_1}\frac{p_1-1}{p_1}p_2^{k_2}\frac{p_2-1}{p_2}\cdots p_m^{k_m}\frac{p_m-1}{p_m} p1k1p1p1−1p2k2p2p2−1⋯pmkmpmpm−1。
再把 p 1 k 1 p 2 k 2 ⋯ p m k m p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m} p1k1p2k2⋯pmkm 拎出来,发现正好等于 n n n,所以结果就变成了:
ϕ ( n ) = n ( p 1 − 1 p 1 ) ( p 2 − 1 p 2 ) ⋯ ( p m − 1 p m ) \phi(n)=n(\frac{p_1-1}{p_1})(\frac{p_2-1}{p_2})\cdots (\frac{p_m-1}{p_m}) ϕ(n)=n(p1p1−1)(p2p2−1)⋯(pmpm−1)
根据这个公式,我们就可以枚举 p i p_i pi 去求解 ϕ ( n ) \phi(n) ϕ(n)。代码:
#include<bits/stdc++.h>
using namespace std;
int n,ans;
int main(){scanf("%d",&n);ans=n;if(n==1)//特判{printf("1\n");return 0;}for(int i=2;i*i<=n;i++){if(n%i==0){ans=ans*(i-1)/i;//公式while(!(n%i))//能整除就一直除下去n/=i;}}if(n>1)//如果n还没有除尽ans=ans*(n-1)/n;printf("%d\n",ans);return 0;
}