欧拉函数模板
点击查看代码
ll euler(ll n) //返回euler(n)
{
ll res=n,a=n;
for(ll i=2; i*i<=a; i++)
{
if(a%i==0)
{
res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出 爆int
while(a%i==0)
a/=i;
}
}
if(a>1)
res=res/a*(a-1);
return res;
}
筛法求欧拉函数模板
点击查看代码
int check[maxn],phi[maxn],prime[maxn];
int main()
{
int n,cnt=0;
n=maxn;
phi[1]=1;
for(int i=2; i<=n; i++)
{
if(!check[i])
{
prime[++cnt]=i;
phi[i]=i-1;
}
for(int j=1; j<=cnt&&prime[j]*i<=n; j++)
{
check[i*prime[j]]=1;
if(i%prime[j])
phi[i*prime[j]]=phi[i]*(prime[j]-1);
else
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
}
}
}
1~n中与n互质的数的和: n/2 * φ(n) (n>1), 1 (n=1)
即不与n互质的数的和:n/2 * (n+1)-n/2 * φ(n)(n>1),0 (n=1)