题意
求 sum_{i=1}^n gcd(i,n) 给定 n（1le nle 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特判一下。
代码语言：javascript复制#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("%lldn",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})
(我觉得这个理解起来不容易)。
代码语言：javascript复制#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("%lldn",ans);
}
return 0;
}
