HDOJ 4135 Co-prime：容斥原理統計互質數個數

問題描述

給定 A, B, N (1 ≤ A ≤ B ≤ 10^15, 1 ≤ N ≤ 10^9)，求區間 [A, B] 中與 N 互質的整數個數。T ≤ 100 組測試。

核心思路：容斥原理

1. 分解 N 的質因數：N = p1^e1 * p2^e2 * ... * pk^ek。只需質因數集合 {p1..pk}，k ≤ 9（因 2×3×5×7×11×13×17×19×23 > 10^9）。
2. 與 N 互質 ⇔ 不被任何 pi 整除。
3. 用容斥原理計算 [1, x] 中不被任一 pi 整除的數個數：f(x) = x - Σ(x/pi) + Σ(x/(pi*pj)) - ...。
4. 答案 = f(B) - f(A-1)。

代碼實現

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

LL A, B, N;
vector primes;

void factorize(LL n) {
    primes.clear();
    for (LL p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            primes.push_back(p);
            while (n % p == 0) n /= p;
        }
    }
    if (n > 1) primes.push_back(n);
}

LL count_coprime(LL x) {  // [1, x] 中與 N 互質的數
    if (x <= 0) return 0;
    LL res = x;
    int k = primes.size();
    for (int mask = 1; mask < (1<> T;
    for (int cas = 1; cas <= T; ++cas) {
        cin >> A >> B >> N;
        factorize(N);
        LL ans = count_coprime(B) - count_coprime(A - 1);
        cout << "Case #" << cas << ": " << ans << '\n';
    }
    return 0;
}

複雜度

• 分解質因數：O(√N) ≈ 3×10^4，T=100 總計 3×10^6，可接受。
• 容斥：O(2^k) ≤ 512，極快。

關鍵點

1. 只需質因數，不需指數。
2. 位圖枚舉子集實現容斥，簡潔高效。
3. A, B 達 10^15，必須用 64 位整數（long long）。
4. count_coprime(0) 返回 0，處理 A=1 邊界。