HDU 3501 Calculation 2 歐拉函數求不互質數和

問題轉化

求 S = Σ_{1≤i<N, gcd(i,N)>1} i (mod 1e9+7)。

等價於：總和 - 互質數和 = N(N-1)/2 - φ(N)·N/2。

數學推導

1. 1 到 N-1 總和：sum_all = N(N-1)/2
2. 與 N 互質的數成對出現：i 與 N-i 同時互質或同時不互質，和為 N
3. 互質數個數為 φ(N)，故互質數和 sum_coprime = φ(N)·N/2
4. 答案 ans = sum_all - sum_coprime = N(N-1 - φ(N))/2

歐拉函數計算

long long phi(long long n) {
    long long res = n;
    for (long long p = 2; p*p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            res = res / p * (p - 1);
        }
    }
    if (n > 1) res = res / n * (n - 1);
    return res;
}

完整代碼

#include <iostream>
using namespace std;
const long long MOD = 1000000007;

long long phi(long long n) {
    long long res = n;
    for (long long p = 2; p*p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            res = res / p * (p - 1);
        }
    }
    if (n > 1) res = res / n * (n - 1);
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    while (cin >> n && n) {
        long long ph = phi(n);
        long long ans = (n % MOD) * ((n - 1 - ph) % MOD) % MOD;
        ans = (ans * 500000004) % MOD; // 乘以 2 的模逆元
        if (ans < 0) ans += MOD;
        cout << ans << '\n';
    }
    return 0;
}

關鍵點

• 模運算中除以 2 需乘以模逆元 inv2 = (MOD+1)/2 = 500000004
• 注意負數取模修正
• φ(N) 計算 O(√N)，N≤1e9 足夠快