对于正整数nn,欧拉函数是小于或等于nn的正整数中与nn互质的数的数目，记作φ(n)φ(n).
φ(1)=1φ(1)=1
求n的欧拉值
首先， 欧拉函数是一个积性函数，当m,nm,n互质时，φ(mn)=φ(m)∗φ(n)φ(mn)=φ(m)∗φ(n)
根据唯一分解定理知 n=pa11∗pa22∗…∗paxxn=p1a1∗p2a2∗…∗pxax
因此 φ(n)=φ(pa11)∗…∗φ(paxx)φ(n)=φ(p1a1)∗…∗φ(pxax)
对于任意一项 φ(pass)=pass−p(as−1)sφ(psas)=psas−ps(as−1)
从定义出发 φ(pass)φ(psas)等于小于或等于passpsas的正整数中与passpsas互质的数的数目
从11到passpsas中共有passpsas个数字
其中与passpsas不互质的有ps,2ps,…,psas−1∗psps,2ps,…,psas−1∗ps ,共psas−1psas−1项
所以 φ(pass)φ(psas) = passpsas - psas−1=pass∗(1−1ps)psas−1=psas∗(1−1ps)
因此
φ(n)=φ(pa11)∗…∗φ(paxx) φ(n)=φ(p1a1)∗…∗φ(pxax) =(pa11−p1a1−1)∗…∗(paxx−pxax−1) =(p1a1−p1a1−1)∗…∗(pxax−pxax−1) =pa11∗(1−1p1)∗pa22∗(1−1p2)∗…∗paxx∗(1−1px) =p1a1∗(1−1p1)∗p2a2∗(1−1p2)∗…∗pxax∗(1−1px) =pa11∗pa22∗…∗paxx∗(1−1p1)∗(1−1p2)∗…∗(1−1px) =p1a1∗p2a2∗…∗pxax∗(1−1p1)∗(1−1p2)∗…∗(1−1px) =n∗∏i=1x(1−1pi)
一.欧拉函数 O(a√∗n)O(a∗n)
对于一个大于1的自然数n来说,由算术基本定理可以将n分解为k个质数的乘积:n=pα11×pα22×…×pαkkn=p1α1×p2α2×…×pkαk
记欧拉函数为ϕ(n)ϕ(n),
欧拉函数ϕ(n)ϕ(n)解决的问题:求解1~n中与n互质的数的个数
互斥:对于两个数a与b,若a和b的公约数只有1时,称a和b互斥
欧拉函数的具体公式:ϕ(n)=n×p1−1p1×p2−1p2×…×pk−1pkϕ(n)=n×p1−1p1×p2−1p2×…×pk−1pk
二.欧拉函数的证明:
证:
利用容斥原理来证明,如不懂,可以先看一下 小学数学:容斥原理
设sum为1~n中与n互斥
基本思路是去掉1~n中所有p1,p2,…,pk的倍数p1,p2,…,pk的倍数
①当p1,p2,…,pk的倍数集合没有交集时p1,p2,…,pk的倍数集合没有交集时
sum=n−np1−np2−…−npksum=n−np1−np2−…−npk
②当p1,p2,…,pk中的任意两个数的倍数集合拥有交集时p1,p2,…,pk中的任意两个数的倍数集合拥有交集时
这时在第①步时,会多减一次pi×pjpi×pj,所以需要加上一次pi×pjpi×pj
因此有sum=n−np1−np2−…−npk+np1×p2+np1×p3+…+npk−1×pksum=n−np1−np2−…−npk+np1×p2+np1×p3+…+npk−1×pk
依次类推有③,④,……
最后将n提出来,就可出现ϕ(n)=n×p1−1p1×p2−1p2×…×pk−1pkϕ(n)=n×p1−1p1×p2−1p2×…×pk−1pk的形式
证毕证毕
三.时间复杂度分析:
算法的瓶颈主要在分解质因数上,分解质因数的时间复杂度为O(a√)O(a),但由于有n组数据,所以时间复杂度为O(a√∗n)O(a∗n)
四.代码
#include using namespace std; int main() { int n; cin>>n; while(n–) { int a,res; cin>>a; res = a; for(int i=2;i<=a/i;i++) { if(a%i0) { while(a%i0) a/=i; res = res / i*(i-1); } } if(a>1) res = res /a*(a-1); cout<<res<<endl; } return 0; }
