POJ - 2480

求\(\sum_{i=1}^{n}\gcd(i,n)~(1\leq n\leq 10^9)\)

显然有

\[\sum_{i=1}^{n}\gcd(i,n)=\sum_{d|n}d\varphi(\frac nd) \]

（考虑 \(\varphi\) 的意义）

然后直接做随便做。

Code

#include<iostream>
#include<cstdio>
using namespace std;

long long getphi(long long x){
    long long ret=1;
    for(int i=2;1ll * i*i<=x;++i){
        if(x%i==0){
            for(ret*=i-1;(x/=i)%i==0;ret*=i);
        }
    }
    return x>1?ret*(x-1):ret;
}

int main(){
    int n;
    while(scanf("%d",&n) != EOF){
        long long ans = 0;
        for(int i = 1; 1ll *  i * i <= n; ++ i){
            if(n % i != 0) continue;
            long long x = getphi(i), y = getphi(n/i);
            ans += x * (n/i) + y * i;
            if(i * i == n) ans -= x * i;
        }
        printf("%lld\n",ans);
    }

    return 0;
}