定义
所有小于n的与n互质的数的个数被称为欧拉函数,记作φ(n)
通式
φ(x)=x(1−1/p1)(1−1/p2)(1−1/p3)(1−1/p4)…..(1−1/pn)
p是x的质因子
可以这样理解:
如果一个数与x互质
那么这个数一定不是x任何一个质因子的倍数
而对x=p1^a1* p2^a2 * ……*pn^an
是p1倍数的数占x的p11
而不是的数占x的1−p11
p2同理,不是p2的倍数的数占x的1−p21
所以说不是x的任意一个质因子的倍数的数有φ(x)=x(1−1/p1)(1−1/p2)(1−1/p3)(1−1/p4)…..(1−1/pn)个
性质
1:对于一个质数x,φ(x)=x-1;
这是显然的吧,如果x是质数那么所有小于它的数都与它互质
2:对于一个数x,1~x中与其互质的数的和为x∗φ(x)/2
证明:
考虑到求gcd的更相损减gcd(a,b)=gcd(a,a−b)
所以所有和x不互质的数都是(a,x−a)(上面gcd式子第二项)这样成对出现
而平均值为x/2,所以所以和x互质的数的平均值也是n/2,而总共有φ(x)个,所以和为x∗φ(x)/2
3:若a,b互质,则φ(a∗b)=φ(a)∗φ(b)(φ为积性函数)
证明:
考虑到a,b,互质,也就是说a,b没有相同的质因子
若设
φ(a)=(1−1/p1)(1−1/p2)(1−1/p3)(1−1/p4)…..(1−1/pn)
φ(b)=(1−1/p1)(1−1/p2)(1−1/p3)(1−1/p4)…..(1−1/pm)(两个p不同,指各自数的质因子)
因为a,b的质因子没有相同的
则根据φ的通式,φ(a∗b)=(a∗b)∗(1−1/p1)(1−1/p2)(1−1/p3)(1−1/p4)…..(1−1/p(n+m))=φ(a)∗φ(b)
4:设n=pk(p为质数) ,则φ(n)=pk−pk−1
证明:因为p为质数,所以n只有p一个质因子
根据公式φ(n)=n∗(1−p1)=pk∗(1−p1)=pk−pk−1
5:若p∣n,p2∣n,则φ(n)=φ(n/p)∗p
证明:因为p∣n,p2∣n,所以n,n/p有相同的质因子,只是系数不同而已,把φ(n)和φ(n/p)按照欧拉函数通式写出来,相除商为p,移项后就为原等式
6:若p∣n且p2!∣n,则φ(n)=φ(n/p)*(p-1)
证明:类似与5可得n,n/p互质,由性质3可得φ(n)=φ(n/p)*φ(p)
因为p为质数,所以φ§=p-1,所以得证
7:Σd∣nφ(d)=n
我也不太会证明,以后有时间再回来补吧
大概就是这些了
关于欧拉筛
O(nlogn)
根据欧拉函数的通式
考虑到一个数只会被其质因子更新,所以我们用类似埃式筛,在筛质数的时候改成更新质数的所有倍数的欧拉函数
模板:(以BZOJ2190仪仗队为例)
inline void init(){
for(int i=1;i<=50000;i++)phi[i]=i;
for(int i=2;i<=50000;i++)
if(phi[i]==i)
for(int j=i;j<=50000;j+=i)
phi[j]=phi[j]/i*(i-1);
}
O(n):
感觉和欧拉筛质数很类似
然后利用欧拉函数的性质(5、6)计算
inline void init(){
phi[1]=1;
for(int i=2;i<=50000;i++){
if(!vis[i]){
pri[++cnt]=i,phi[i]=i-1;
}
for(int j=1;j<=cnt&&pri[j]*i<=50000;j++){
vis[pri[j]*i]=1;
if(i%pri[j]==0){
phi[i*pri[j]]=phi[i]*pri[j];break;
}
else phi[i*pri[j]]=phi[i]*phi[pri[j]];
}
}
}