51Nod1040 最大公约数之和

欧拉函数

51Nod

对于 $\gcd(i,n)=d$ ，我们可以知道 $\gcd(\frac{i}{d},\frac{n}{d})=1$。也就是 $\frac{i}{d}$ 与 $\frac{n}{d}$ 互质。那么，枚举每个最大公因数 $d$，求一下欧拉函数就行了。注意每次枚举 $d$ 到 $\sqrt{n}$ 就行了，然后再处理 $\frac{n}{d}$。

#include <iostream>
#include <cmath>
#include <cstdio>
typedef long long LL;
int N;
LL Ans;
LL Phi(int x)
{
    LL res = x;
    int n = sqrt(x);
    for(int i = 2; i <= n; ++i)
    {
        if(x % i == 0) 
        {
            res = res / i * (i - 1);
            while(x % i == 0) x /= i;
        }
    }
    if(x > 1) res = res / x * (x - 1);
    return res;
}
int main()
{
    scanf("%d", &N);
    int n = sqrt(N);
    for(int i = 1; i <= n; ++i)
    {
        if(N % i != 0) continue;
        Ans += LL(i) * Phi(N / i);
        if(i * i != N) Ans += LL(N / i) * Phi(i);   
    }   
    printf("%lld\n", Ans);
}