-
求单个欧拉函数值
直接套用欧拉函数的普通表达式(唯一质因子分解)
ll euler(ll n)
{
ll ans=n;
for(ll i=2;i*i<=n;i++)
{
if(n%i==0)
{
ans=ans/i*(i-1);
while(n%i==0) n/=i;
}
}
if(n!=1) ans=ans/n*(n-1);
return ans;
}
-
求多个欧拉函数值
如果还按照求单个函数值的方法求的话肯定会超时
i.第一种方法要用到欧拉函数的两个性质:(这种方法我尽量理解去记(;´༎ຶД༎ຶ`),时间复杂度比第二种小)
- n%a==0 && (n/a)%a==0 则 ,a是质数
- n%a==0 && (n/a)%a!=0 则 ,a是质数
ll phi[100],dive[100];//分别对应素数表和欧拉函数值
for(ll i=1;i<=n;i++)
phi[i]=i;
for(ll i=2;i*i<=n;i++)
{
if(phi[i]==i)
for(ll j=i*i;j<=n;j+=i)
phi[j]=i;
}
for(ll i=2;i<=n;i++)
{
if(i%phi[i]==0 && (i/phi[i])%phi[i]==0)
dive[i]=dive[i/phi[i]]*phi[i];
if(i%phi[i]==0 && (i/phi[i])%phi[i]!=0)
dive[i]=dive[i/phi[i]]*(phi[i]-1);
}
ii.第二种方法要用到欧拉函数的积性
- 如果m和n互质,则
- 如果n含有质因子k,则
代码来源:https://blog.csdn.net/acerandaker/article/details/80722630
void getphi()
{
int vis[M],phi[M],pri[M],tot;
for(int i=2;i<=n;i++)
{
if(!vis[i])//先判断i是不是素数
{
pri[++tot]=i;
phi[i]=i-1;//当 i 是素数时小于i的所有大于零的数都和i互素
}
for(int k=1;k<=tot;k++)
{
if(i*pri[k]>M) break;
vis[i*pri[k]]=1;//按照筛素数,筛掉i的倍数
if(i%pri[k]==0)//如果有一个质数是i的因子,那么phi(i*pri[k])=phi(i)*pri[k]
{
phi[i*pri[k]]=phi[i]*pri[k];break;
}
else phi[i*pri[k]]=phi[i]*(phi[pri[k]]);
//利用了欧拉函数的积性,两个数互质,那么phi(i*k)=phi(i)*phi(pri[k])
}
}
}