欧拉函数相关
说是数论只会gcd的我其实真的遇到,连gcd都不会,怎么办呢!那就看欧拉函数压压惊吧。
一、定义:
一个正整数的欧拉函数定义为小于它且与它互质的正整数的个数。(φ(1)=1)
二、性质:
1、对于质数p,φ(p)=p-1
2、\(\varphi (x)=x(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})(1-\frac{1}{p_{3}})……(1-\frac{1}{p_{n}})\),其中p1,p2,p3,…,pn为x的质因子
3、若\(n=p^{k}\),则\(\varphi (n)=p^{k}-p^{k-1}=(p-1)p^{k-1}\)
4、当n为奇数时,φ(2n)=φ(n)
5、欧拉函数是积性函数,若p,q互质,则φ(pq)=φ(p)φ(q)
6、推广:设p为素数且p|n,若p^2|n,则\(\varphi (n)=\varphi (\frac{n}{p})*p\),否则\(\varphi (n)=\varphi (\frac{n}{p})*(p-1)\)
三、应用
1、求单个数的欧拉函数值
求单个数n的欧拉函数值思路就是先将n分解质因数然后利用性质3和5相乘计算
复杂度\(O(\log{N})\)
1 2 3 4 5 6 7 8 9 10 11 12 |
int eular(int n) { int ret=1,i; for(i=2;i*i<=n;i++){ if(n%i==0){ n/=i,ret*=i-1; while(n%i==0) n/=i,ret*=i; } } if(n>1) ret*=n-1; return ret; } |
2、求1-n的欧拉函数表
与素数筛类似,一边筛素数一边计算欧拉函数值,具体的实现利用了上述性质6
复杂度\(O(N)\)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#define N 10000000 bool not_prime[MAXN]; int tot=0,prime[MAXN],phi[MAXN];//prime记录素数,phi记录欧拉函数值 void init() { int i,j; phi[1]=1; for(i=2;i<=N;i++){ if(!not_prime[i]){ phi[i]=i-1; prime[++tot]=i; } for(j=1;j<=tot&&i*prime[j]<=N;j++){ not_prime[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); } } } } |
3、指数降幂公式
\(A^{n}\mod{p}=A^{n\mod{\varphi (p)+\varphi (p)}}\mod{p}\)
丢个公式就跑,真tm刺激
本文出自shad0w_walker,转载时请注明出处及相应链接。
本文永久链接: https://www.sdwalker.com/archives/477.html