【POJ 2480】Longge's problem（欧拉函数）
【POJ 2480】Longge's problem（欧拉函数）
饶文津
发布于 2020-06-02 15:39:27
发布于 2020-06-02 15:39:27
题意
求 \sum_{i=1}^n gcd(i,n) 给定 n（1\le n\le 2^{32}) 。
题解
欧拉函数 φ(x) ：1到x-1有几个和x互质的数。
gcd(i,n)必定是n的一个约数。
若p是n的约数，那么gcd(i,n)==p的有φ(n/p)个数，因为要使gcd(i,n)==p，i/p和n/p必须是互质的。
那么就是求i/p和n/p互质的i在[1,n]里有几个，就等价于 1/p，2/p，...，n/p 里面有几个和n/p互质，即φ(n/p)。
求和的话，约数为p的有φ(n/p)，所以就是p*φ(n/p)，同时把约数为n/p的加上去，i*i==n特判一下。
#include<cstdio>
#include<cmath>
#define ll long long
ll n,ans,i;
ll euler(int x)
{
int res=x;
for(int i=2; i<=sqrt(x); i++)
if(x%i==0)
{
res=res/i*(i-1);
while(x%i==0)x/=i;
}
if(x>1)res=res/x*(x-1);
return res;
}
int main()
{
while(~scanf("%lld",&n))
{
ans=0;
for(i=1; i<sqrt(n); i++)if(n%i==0)
ans+=i*euler(n/i)+n/i*euler(i);
if(i*i==n)ans+=i*euler(i);
printf("%lld\n",ans);
}
}另外一种做法是:
素数a有φ(a^b)=a^b-a^(b-1)=(a-1)*a^b。
且有 \sum_{i=1}^n gcd(i,a^b)
=φ(a^b)+a*φ(a^(b-1))+...+(a^b)*φ(1)
=b*(a-1)*(a^(b-1))+a^b。
由n=p_1^{k_1}+p_2^{k_2}+...+p_s^{k_s}，
可得\sum_{i=1}^n gcd(i,n)
=\sum_{i=1}^n gcd(i,p_1^{k_1})*\sum_{i=1}^n gcd(i,p_2^{k_2})*...*\sum_{i=1}^n gcd(i,p_s^{k_s})
(我觉得这个理解起来不容易)。
#include<cstdio>
long long n,i,k,pk,ans;
int main ()
{
while(scanf("%lld",&n)!=EOF)
{
ans=1;
for(i=2;i*i<=n;++i)
{
k=0,pk=1;
while(n%i==0)
{
n=n/i;
k++;
pk*=i;
}
ans*=k*(pk-pk/i)+pk;//φ[p^k]=k×(p^k-p^(k-1))+p^k
}
if(n>1)ans*=2*n-1;
printf("%lld\n",ans);
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016-07-21 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录