记录编号	600732	评测结果	AAAAAAAAAA
题目名称	[河南省队2012] 最大公约数和	最终得分	100
用户昵称	汐汐很希希	是否通过	通过
代码语言	C++	运行时间	0.029 s
提交时间	2025-05-12 20:36:21	内存使用	3.69 MiB

#include<bits/stdc++.h>
using namespace std;
long long sum=0;
int phi(int a)
{
    long long ans=a;
    for(int i=2;i*i<=a;i++)
    {
        if(a%i==0)
        {
            ans=ans/i*(i-1);
            while(a%i==0) a/=i;
        }
    }
    if(a>1) ans=ans/a*(a-1);
    return ans;
}
int main()
{
    freopen("gcdsum.in","r",stdin);
    freopen("gcdsum.out","w",stdout);
    
    int n;
    cin>>n;
    for(long long i=1;i*i<=n;i++)
    {
        if(n%i==0){
    
            if(i*i==n) sum+=phi(i)*i;
            else sum+=phi(i)*(n/i)+phi(n/i)*i;
        }
    }
    cout<<sum<<endl;
    return 0;
}