又是一个奇怪的解法。
考虑枚举$x$,并求解有多少$gcd(i,n)=x$.
$x$必然是$n$的某个约数，是$O(\sqrt n)$级别。
数量等价于$gcd(i/x,n/x)=1$.这恰是$\varphi(n/x)$.如果暴力求解$\varphi(n/x)$，时间复杂度又是$O(\sqrt n)$,总时间复杂度仍是$O(n)$,TLE.
考虑求解欧拉函数是个分解质因数的过程，可以先筛出到$\sqrt n$的素数表，分解时直接使用即可。将求解欧拉函数的时间降为$O(\frac{\sqrt n}{log n})$,总时间复杂度$O(\frac{n}{log n})$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 1000011
ll p[MAXN],phi[MAXN],cnt=0;
bool vis[MAXN];
void sieve()
{
    vis[1]=1,phi[1]=0;
    for(ll i=2;i<MAXN;++i)
    {
        if(!vis[i])
        {
            p[++cnt]=i;
            phi[i]=i-1;
        }
        for(ll j=1;j<=cnt&&i*p[j]<MAXN;++j)
        {
            vis[i*p[j]]=1;
            phi[i*p[j]]=phi[i]*(p[j]-1);
            if(i%p[j]==0)
            {
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }
        }
    }
}
ll calc_phi(ll n)
{
    ll ans=n;
    for(ll i=1;p[i]*p[i]<=n;++i)
    {
        ll x=p[i];
        if(n%x==0)
        {
            ans=ans/x*(x-1);
            while(n%x==0)n/=x;
        }
    }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}
int main()
{
    sieve();
    ll n;
    scanf("%lld",&n);
    ll ans=calc_phi(n)+n;
    for(ll i=2;i*i<=n;++i)
        if(n%i==0)
        {
            ll tmp=n/i;
            ans+=i*calc_phi(tmp);
            if(i*i==n)continue;
            tmp=i;
            ans+=(n/i)*calc_phi(tmp);
        }
    printf("%lld",ans);
    return 0;
}