欧拉函数定义
1∼N中与N 互质的数的个数被称为欧拉函数,记为ϕ(N)。
在算数基本定理中:N=p1c1×p2c2×⋯pmcm,则:
ϕ(N)=N×p1p1−1×p2p2−1×⋯×pmpm−1=N×质数p∣N∏(1−p1)
证明
设p1 是 N的质因子,1∼N中p1的倍数有p1,2P1,3p1,⋯,(N/p1)×p1,共N/p1个。同理。若p2是N的质因子,1∼N中p2的倍数有N/p2个。这N/p1+N/p2个数中,其中既是p1的倍数,又是p2的倍数的数有N/(p1⋅p2) 个。根据容斥原理,N中去掉p1和p2的倍数:
N−p1N−p2N+p1⋅p2N=N(1−p11−p21+p1⋅p21)=N⋅(1−p11)(1−p21)
类似的,N的全部质因子都能使用容斥原理实现,得到与N互质的数的个数。
性质
- ∀n>1,1∼n中与n互质的数的和为n×ϕ(n)/2。
- 若a,b互质,则ϕ(ab)=ϕ(a)⋅ϕ(b)
证明性质1
若x为与n互质的数,则根据更相减损术原理,gcd(n,x)=gcd(n,n−x)=1 。故,与n互质的x,n-x成对出现,总和为(x+n−x)×ϕ(n)/2=n×ϕ(n)/2。
性质1证毕。
证明性质2
算数基本定理中:
a=p1c1⋅p2c2⋯pmcm
b=q1d1⋅q2d2⋯qkdk
ϕ(a)=a⋅(1−p11)(1−p21)⋯(1−pm1)
ϕ(b)=b⋅(1−q11)(1−q21)⋯(1−qk1)
∵a、b互质
∴p1⋯pm,q1⋯qk各不相同
∴a⋅b=p1c1⋅p2c2⋯pmcm⋅q1d1⋅q2d2⋯qkdk
ϕ(ab)=a⋅b⋅(1−p11)(1−p21)⋯(1−pm1)⋅(1−q11)(1−q21)⋯(1−qk1)
ϕ(ab)=ϕ(a)⋅ϕ(b)
性质
若p是质数
- ϕ(p)=p−1
- 若p∣i,ϕ(i×p)=p×ϕ(i)
- 若p∤i,ϕ(i×p)=(p−1)×ϕ(i)
证明性质3
因为p是质数,p与1∼p−1 的每个数都互质,故ϕ(p)=p−1。
证明性质4
∵p为质数,p∣i
∴i=p1c1⋯pca⋯pmcm
∴ϕ(i)=i×(1−p11×⋯×(1−p1)×⋯×(1−pm1)
i×p=p1c1⋯pca+1⋯pmcm
ϕ(i×p)=i×p×(1−p11)×⋯×(1−p1)×⋯×(1−pm1)
∴ϕ(i×p)=p×ϕ(i)
性质4证毕
证明性质5
∵p为质数,p∤i
∴p,i 互质
∴ϕ(p⋅i)=ϕ(p)⋅ϕ(i)
∵p为互质
∴ϕ(p)=p−1
∴ϕ(p⋅i)=(p−1)×ϕ(i)
性质5证毕
代码实现
质因数分解
int phi(int x){//求x的欧拉函数值
int ans=x;
for(int i=2;i*i<=x;i++){//分解x的质因数
if(x%i==0){
ans=ans/i*(i-1);
while(x%i==0){
x/=i;
}
}
}
if(x>1) ans=ans/x*(x-1);
return ans;
}
线性筛
int erla(int n){//利用线性筛更新欧拉函数值
int cnt=0;//质数个数
v[0]=v[1]=1;//标记0和1为非质数
phi[1]=1;//记录1的欧拉函数值为1
for(int i=2;i<=n;i++){//遍历2~n
if(!v[i]){//i是质数
prime[cnt++]=i;//存储i到质数表
phi[i]=i-1;//性质3: p是质数,phi(p)=p-1
}
//遍历质数表
for(int j=0;j<cnt&&prime[j]*i<=n;j++){
v[prime[j]*i]=1;//标记质数与i的乘积为非质数
if(i%prime[j]==0){//性质4:若p%i==0,phi(i*p)=p*phi(i)
phi[i*prime[j]]=prime[j]*phi[i];
break;
}else{//性质5:若p%i!=0,phi(i*p)=(p-1)*phi(i)
phi[i*prime[j]]=(prime[j]-1)*phi[i];
}
}
}
return cnt;//返回质数个数
}