∵∑gcd(i, N)(1<=i <=N)

=k1*s(f1)+k2*s(k2)+...+km*s(km) {ki是N的约数，s(ki)是满足gcd(x,N)=ki(1<=x<=N)的x的个数}

∴gcd(x,N)=ki (1<=x<=N)  <=>  gcd(x/ki,N/ki)=1 (1<=x/ki<=N/ki)

gcd(x/ki,N/ki)=1 (1<=x/ki<=N/ki) 的x的个数 即为φ(N/ki)

∴ans=∑φ(N/ki)*ki

∴O(sqrt(N))枚举约数即可。

1 #include
     
       2 #include
      
        3 using namespace std; 4 typedef long long ll; 5 ll n,ans; 6 int phi(ll x) 7 { 8     ll res=x; 9     for(ll i=2;i*i<=x;i++)10       if(x%i==0)11         {12           res=res/i*(i-1);13           while(x%i==0) x/=i;14         }15     if(x>1) res=res/x*(x-1);16     return res;17 }18 int main()19 {20     scanf("%lld",&n);21     for(ll i=1;i*i<=n;i++) if(n%i==0) ans+=(phi(n/i)*i+phi(i)*(n/i));22     printf("%lld\n",ans);23     return 0;24 }