欧拉函数算法的实现

对于正整数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;
}