欧拉函数
我们用$/phi(n)$表示欧拉函数
定义:$/phi(n)$表示对于整数$n$,小于等于$n$中与$n$互质的数的个数
性质
1.$/phi(n)$为积性函数
2.$/sum_{d|n}/phi(d)=n$
3.$1$到$n$中与$n$互质的数的和为$n*/dfrac{/phi(n)}{2}(n>1)$
计算方法
$/sqrt(n)$计算单值欧拉函数
假设我们需要计算$/phi(n)$
分情况讨论
1.当$n=1$时
很明显,答案为$1$
2.当$n$为质数时
根据素数的定义,答案为$n-1$
(仅有$n$与$n$不互质)
3.当$n$为合数时
我们已经知道了$n$为素数的情况
不妨对$n$进行质因数分解
设$n=a_1^{p_1}*a_2^{p_2}...*a_k^{p_k}$
假设$k=1$
那么$/phi(p^k)=p^k-p^{k-1}$
证明:
考虑容斥,与一个数互素的数的个数就是这个数减去与它不互素的数的个数
因为$p$是素数,所以在$p^k$中与其不互素的数为$1*p$,$2*p$....$p^{k-1}*p$,有$p^{k-1}$个
得证
当$k/neq 1$时
$$/phi(n)$$
$$=/varphi /left( a^{p_{1}}_{1}a^{p_{2}/ldots }_{2}a^{Pk}_{k}/right)$$
$$=/prod ^{k}_{i=1}a^{P_i}-a^{P_{i}-1}_{i}$$
$$=/prod ^{k}_{i=1}a^{Pi}_{i}(1-/dfrac {1}{p_{i}})$$
$$=n*/prod ^{k}_{i=1}(1-/dfrac {1}{p_{i}})$$
#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#define LL long long using namespace std;int main(){ LL N; while(cin>>N&&N!=0) { int limit=sqrt(N),ans=N; for(int i = 2; i <= limit ; ++i) { if(N%i==0) ans=ans/i*(i-1); while(N%i==0) N=N/i; } if(N>1) ans=ans/N*(N-1); printf("%d/n",ans); } return 0;}
线性筛
因为欧拉函数是积性函数
因此可以使用线性筛法
性质1
若$p$为素数,则$/varphi /left( p/right) =p-1$
证明:
在$1-p$中,只有$(p,p)/neq1$
性质2
若$i mod p /neq 0$,且$p$为素数
则$/varphi /left( i*p/right) =/varphi /left( i/right) */varphi /left( p/right)$
$=/varphi /left( i/ast p/right) =/varphi /left( i/right) /ast /left( p-1/right)$
这一步同时利用了性质1和欧拉函数的积性
性质3
若$i mod p = 0$,且$p$为素数,
则$/varphi /left( i/ast p/right) =/varphi /left( i/right) /ast p$
证明:
没怎么看懂,丢一个链接
http://blog.csdn.net/Lytning/article/details/24432651
#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#define LL long long using namespace std;const int MAXN=1e6+10;int prime[MAXN],tot=0,vis[MAXN],phi[MAXN],N=10000;void GetPhi(){ for(int i=2;i<=N;i++) { if(!vis[i]) { prime[++tot]=i; phi[i]=i-1; } for(int j=1;j<=tot&&prime[j]*i<=N;j++) { vis[ i*prime[j] ] = 1; if(i%prime[j]==0) { phi[ i*prime[j] ]=phi[i]*prime[j]; break; } else phi[ i*prime[j] ]=phi[i]*(prime[j]-1); } }}int main(){ GetPhi(); cin>>N; printf("%d/n",phi[N]); return 0;}
例题
放两道水题
http://poj.org/problem?id=2407
题解
http://poj.org/problem?id=2478
题解