一文读懂欧拉函数-数据与算法之美
欧拉函数φ(N)表示小于或等于N的正整数中与N互质的数的个数石柑子。又称φ函数、欧拉商数陆维梁。
下面介绍欧拉函数的几个性质：
我们根据这几个性质就可以求出欧拉函数。
基本思路是首先置φ(N)=N，然后再枚举素数p陈乃娴，将p的整数倍的欧拉函数φ(kp)进行如下操作唐子豪。
代码如下：
#include
usingnamespacestd;
constintMAX=1024;
intN;
intp[MAX],phi[MAX];
intmain()
{
cin>>N;
for(inti=1;i<=N;i++)// 初始化
{p[i]=1;phi[i]=i;}
p[1]=0;// 1不是素数
for(inti=2;i<=N;i++)// 筛素数
{
if(p[i])
{
for(intj=i*i;j<=N;j+=i)
{p[j]=0;}
}
}
for(inti=2;i<=N;i++)// 求欧拉函数
{
if(p[i])
{
for(intj=i;j<=N;j+=i)// 处理素因子p[i]
{
phi[j]=phi[j]/i*(i-1);// 先除后乘，防止中间过程超出范围
}
}
}
cout<<"Primes: "<<endl;
for(inti=1;i<=N;i++)
{if(p[i]){cout<<i<<" ";}}
cout<<endl;
cout<<"Euler Phi Function: "<<endl;
for(inti=1;i<=N;i++)
{cout<<phi[i]<<" ";}
return0;
}
以上是关于欧拉函数的求法踏平东京 ，对于它的应用，这里暂且介绍一个——求解原根的个数星宿会战。
对于原根的定义滚石琴行，我们可以这样来叙述：
若存在一个实数a，使得( a^i ) mod N缺德社,a∈{1丛林巨蜥 ,2,3大药天香 ,?孤帆窑 闹婚记 ,N}的结果各不相同猎狼联线，我们就成实数a为N的一个原根全城高考。
巩天阔原根的个数等于φ(φ(N))。这样我们就可以很方便的求出原根的个数吴苇珊 。
代码如下：
#include
#include
usingnamespacestd;
typedefunsignedlonglongull;
ullN;
ull phi(ullx);
intmain()
{
cin>>N;
cout<<phi(phi(N))<<endl;
return0;
}
ull phi(ullx)
{
ullans=x;
ullm=(ull)sqrt(x);
for(ulli=2;i<<=m;i++)
{
if(x%i==0)// 求素因子
{
ans=ans/i*(i-1);// 运用通项求解欧拉函数
while(x%i==0)// 每个素因子只计算一次
{x/=i;}
}
}
if(x>1)// 防质数
{ans=ans/x*(x-1);}
returnans;
}
转自：ivy-end
http://www.ivy-end.com/archives/1021
