龙哥的问题

这题思路清晰就好了.
最大公约数即为因子,我们把n的因子求出来即可,然后根据欧拉的定理即是答案了.
我们知道求gcd(1a,n)=i.就等同于gcd(1a/i,n/i)=1.
然后就是统计答案了.
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e3;
ll ys[N];
inline ll get_phi(ll x)//得到x的欧拉函数.
{
    ll cnt=x;
    for(ll i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            while(x%i==0) x/=i;
            cnt=cnt/i*(i-1);
        }
    }
    if(x>1)
    {
        cnt=cnt/x*(x-1);
    }
    return cnt;
}

int main()
{
    ll n,cnt=0,ans=0;
    cin>>n;
    for(ll i=1;i*i<=n;i++)
    {
        if(n%i==0)  {ys[cnt++]=i;if(i==n/i) continue;ys[cnt++]=n/i;}
    }
    for(ll i=0;i<cnt;i++)
    {
        ans+=ys[i]*get_phi(n/ys[i]);
    }
    cout<<ans<<endl;
    return 0;
}