欧拉函数板子有哪些应用场景？

本文共计292个文字，预计阅读时间需要2分钟。

直接计算一个数的欧拉值，复杂度O(sqrt(n)) + ll + Euler(ll+n) { ll res=n; for(ll i=2; i*i 1) res=res / (n-1) * n; return 线性筛算1到n的欧拉值

直接算一个数的欧拉值，复杂度O（sqrt(n)）

ll Euler(ll n){
ll res = n;
for(ll i = 2;i*i <= n;i++){
if(n%i == 0) res = res/i*(i-1);//防止溢出
while(n%i == 0) n /= i;
}
if(n > 1) res = res/n*(n-1);
return

线性筛算1到n的欧拉值

void Init(){
euler[1]=1;
for(int i=2;i<MAXN;i++)
euler[i]=i;
for(int i=2;i<MAXN;i++)
if(euler[i]==i)
for(int j=i;j<MAXN;j+=i)
euler[j]=euler[j]/i*(i-1);//防止中间数据溢出

筛素数同时筛欧拉值

int tot,pri[MAX],phi[MAXN];
bool mark[MAXN];

void getphi()
{
phi[1]=1;
for(int i=2;i<=n;i++)
{
if(!mark[i]){phi[i]=i-1;pri[++tot]=i;}
for(int j=1;j<=tot;j++)
{
int x=pri[j];
if(i*x>n)break;
mark[i*x]=1;
if(i%x==0){phi[i*x]=phi[i]*x;break;}
else phi[i*x]=phi[i]*phi[x];
}
}
}