BZOJ 2301 [HAOI2011] Problem b：容斥 + 莫比烏斯反演求 GCD 計數

問題描述

n ≤ 50,000 個查詢，每查詢給 a, b, c, d, k（≤ 50,000）。求滿足 a ≤ x ≤ b, c ≤ y ≤ d, gcd(x, y) = k 的數對 (x, y) 個數。

容斥原理降維

矩形查詢可拆解為四個前綴查詢：

F(b, d) - F(a-1, d) - F(b, c-1) + F(a-1, c-1)

其中 F(n, m) = |{1 ≤ x ≤ n, 1 ≤ y ≤ m : gcd(x, y) = k}|。

令 x = k * x', y = k * y'，則 gcd(x', y') = 1，且 1 ≤ x' ≤ n/k, 1 ≤ y' ≤ m/k。問題轉化為：求 1 ≤ x ≤ N, 1 ≤ y ≤ M 且 gcd(x, y) = 1 的數對數。

莫比烏斯反演核心

定義 f(d) = gcd(x, y) = d 的數對數，g(d) = d | gcd(x, y) 的數對數 = ⌊N/d⌋ * ⌊M/d⌋。

莫比烏斯反演：f(1) = ∑_{d=1}^{min(N,M)} μ(d) * g(d) = ∑ μ(d) * ⌊N/d⌋ * ⌊M/d⌋。

整除分塊優化 O(√N)

⌊N/d⌋ 和 ⌊M/d⌋ 只有 O(√N) 種不同取值。預計算 μ 前綴和 `sum[i] = ∑_{k=1}^i μ(k)`。

分塊求和：

int calc(int n, int m) {
    if (n > m) swap(n, m);
    int ans = 0;
    for (int i = 1, pos; i <= n; i = pos + 1) {
        pos = min(n / (n / i), m / (m / i));
        ans += (sum[pos] - sum[i-1]) * (n / i) * (m / i);
    }
    return ans;
}

完整流程

1. 線性篩預計算 μ(1..50000) 及前綴和。
2. 每查詢：a--, c--；a/=k, b/=k, c/=k, d/=k。
3. Ans = calc(a, c) + calc(b, d) - calc(a, d) - calc(b, c)。
4. 輸出 Ans。

複雜度

預處理 O(MAXK) = 50,000。單查詢 O(√(MAXK)) ≈ 224。50,000 查詢總操作 ~1.1e7，極快。內存 O(MAXK)。

代碼亮點

• 線性篩同時得 μ 和質數表，O(N)。
• 整除分塊模板代碼可復用（`pos = min(n/(n/i), m/(m/i))`）。
• 整數運算無溢出風險（50000² = 2.5e9 < 2³¹）。

總結

本題是「容斥 + 莫比烏斯反演 + 整除分塊」經典組合拳，展示了如何將二維 GCD 計數問題層層化簡為 O(√N) 可解形式，是數論競程必修範例。