1040 最大公约数之和
题目连接:
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1040
Description
给出一个n,求1-n这n个数,同n的最大公约数的和。比如:n = 6
1,2,3,4,5,6 同6的最大公约数分别为1,2,3,2,1,6,加在一起 = 15
Input
1个数N(N <= 10^9)
Output
公约数之和
Sample Input
6
Sample Output
15
Hint
题意
题解:
与n的公约数,肯定是n的因子
那么我们枚举因子x就好了,显然这个因子的对答案的贡献就是gcd(n,i)=x的个数
gcd(n,i)=x的个数,就是gcd(n/x,i/x)=1的个数,那么就是求phi(n/x)啦
这个就直接莽一波就好了
代码
#include<bits/stdc++.h>
using namespace std;
long long phi(long long n)
{
long long tmp=n;
for(long long i=2;i*i<=n;i++)
if(n%i==0)
{
tmp/=i;tmp*=i-1;
while(n%i==0)n/=i;
}
if(n!=1)tmp/=n,tmp*=n-1;
return tmp;
}
int main()
{
long long n,ans=0;
cin>>n;
for(int i=1;i*i<=n;i++)
{
if(n%i==0)
{
ans+=1ll*i*phi(n/i);
if(i*i!=n)
ans+=1ll*n/i*phi(i);
}
}
cout<<ans<<endl;
}