题目大意

给定一个整数$n$,你需要求出$∑^{n}_{i=1}gcd(i,n)$

数据范围

$1\leqslant n\leqslant 2^{32}$

题解

首先清楚一个性质：$gcd(a,b)=k$, $gcd(\frac{a}{k},\frac{b}{k})=1$

然后，枚举n的每一个约数$p_i$, $[1..\frac{n}{p_i}]$ 中与$\frac{n}{p_i}$互质的数的个数，即$\varphi(\frac{n}{p_i})$。

最后答案加上$p_i\times \varphi(\frac{n}{p_i})$

程序

#include<cstdio>
#include<cmath>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ll long long
using namespace std;

ll n,ans;
int m;

inline ll getphi(ll x){
    ll y=x;
    For(i,2,m)
        if (!(x%i)){
            y=y/i*(i-1);
            while (!(x%i)) x/=i;
        }
    if (x>1) y=y/x*(x-1);
    return y;
}

int main(){
    scanf("%lld",&n);m=sqrt(n);
    For(i,1,m)
        if (!(n%i)){
            ans+=(ll)i*getphi(n/i);
            if (i*i<n) ans+=(ll)(n/i)*getphi(i);
        }
    printf("%lld\n",ans);
    return 0;
}