嗯A了道水题（其实在学polya的时候做过类似的）

题意很裸，就是求sigma(gcd(i,n))，那很容易发现很多i和n的gcd是相等的，那我们就枚举gcd，然后将它的phi求出来，那(n/i)*phi(i)就将全部gcd为(n/i)的值给求出来了，同理phi(n/i)也一样，那先预处理一下素数，然后O(sqrt(n))枚举就行了。

#include
     
      #include
      
       #include
       
        using namespace std;typedef long long LL;bool v[1100000];int pr,prime[1100000];void linear_prime(){    memset(v,true,sizeof(v));    for(int i=2;i<=1000000;i++)    {        if(v[i]==true)prime[++pr]=i;        for(int j=1;j<=pr&&i*prime[j]<=1000000;j++)        {            v[i*prime[j]]=false;            if(i%prime[j]==0)break;        }    }}LL n;LL phi(LL x){    LL ans=x;    for(int i=1;prime[i]*prime[i]<=x;i++)    {        if(x%prime[i]==0)        {            ans=ans-ans/prime[i];            while(x%prime[i]==0)x/=prime[i];        }    }    if(x!=1)ans=ans-ans/x;    return ans;}int main(){    linear_prime();    scanf("%lld",&n);    LL ans=0;    for(int i=1;i*i<=n;i++)//枚举gcd     {        if(n%i==0)        {            ans+=phi(i)*(n/i);            if(i*i!=n)ans+=phi(n/i)*i;        }    }    printf("%lld\n",ans);    return 0;}