HDU 1695 GCD：容斥原理 + 質因數分解計算互質對數

問題描述

給定 a,b,c,d,k，求滿足 gcd(x,y) = k 的數對 (x,y) 個數，其中 a ≤ x ≤ b, c ≤ y ≤ d。多測試用例。

轉化

gcd(x,y)=k ⇔ gcd(x/k, y/k)=1 且 x,y 均為 k 的倍數。
令 b' = b/k, d' = d/k（向下取整），問題轉化為：
在 [1, b'] × [1, d'] 中求互質數對個數。
設 b' ≤ d'（否則交換），總數對 = b' * d'。
答案 = 總數對 - 不互質數對個數。

容斥原理計算不互質數對

對每個 x ∈ [1, b']，求 y ∈ [1, d'] 中與 x 不互質的個數。
x 的質因子集合為 {p₁, p₂, ..., pₘ}。
y 被至少一個 pᵢ整除的個數 = 容斥原理：
sum_{非空子集 S} (-1)^(|S|+1) * floor(d' / prod(S))。
對所有 x 累加，得不互質總數。
預處理 1~100000 的質因子列表（去重）。

代碼實現 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXV = 100000;
vector prime_factors[MAXV+1];
void init_factors() {
    for (int i = 2; i <= MAXV; ++i) {
        if (prime_factors[i].empty()) { // i 是質數
            for (int j = i; j <= MAXV; j += i)
                prime_factors[j].push_back(i);
        }
    }
}
long long solve_case(long long a, long long b, long long c, long long d, long long k) {
    if (k == 0) return 0;
    b /= k; d /= k;
    if (b > d) swap(b, d);
    // 總數對
    long long total = b * d;
    // 不互質數對
    long long not_coprime = 0;
    for (int x = 1; x <= b; ++x) {
        const auto& pf = prime_factors[x];
        int m = pf.size();
        // 枚舉非空子集
        for (int mask = 1; mask < (1<> T;
    for (int tc = 1; tc <= T; ++tc) {
        long long a,b,c,d,k; cin >> a >> b >> c >> d >> k;
        cout << "Case " << tc << ": " << solve_case(a,b,c,d,k) << '\n';
    }
    return 0;
}

複雜度

• 預處理：O(MAXV log log MAXV) 篩法記錄質因子。
• 每測試用例：O(b × 2^ω(x))，ω(x) ≤ 6（100000 內最多 6 個不同質因子），b ≤ 100000。最壞約 100000 × 64 = 6.4e6，可接受。

關鍵點

• gcd(x,y)=k 轉化為互質問題，範圍縮小 k 倍。
• 容斥原理在質因子集合上枚舉子集，計算被整除數個數。
• 預處理質因子列表避免重複分解。

這題是「區間互質對計數」的經典模板，結合質因子預處理與容斥原理，高效解決多查詢問題。