【題解】T2498 [SDOI2012] Longge的问题

【題目敘述】https://nanti.jisuanke.com/t/T2498
【解題想法】歐拉函數
给定一个整数N,你需要求出 ∑gcd(i, N),(1<=i <=N)。

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

long long n, ans, sq;

int phi(int x){
    //歐拉函數
    int ret = x, sq = sqrt(x);
    for (int j = 2; j <= sq; j++){
        if (x % j == 0){
            while (x % j == 0){
                x /= j;
            }
            ret -= ret / j;
        }
    }
    if (x != 1) ret -= ret / x;
    return ret;
}

int main() {
    cin >> n;
    sq = sqrt(n);
    for (int i = 1; i <= sq; i++){
        if (n % i == 0){
            ans += (n/i) * phi(i);
            if (i * i != n) ans += i * phi(n/i);
        }
    }
    cout << ans;
}


分享本文 Share with friends