HDU 4746 Mophues：莫比烏斯反演 + 線性篩前綴和優化

HDU 4746 Mophues：莫比烏斯反演 + 線性篩前綴和優化

Q ≤ 5000 組查詢，每組給 n, m, P (≤ 5e5)。求 1≤a≤n, 1≤b≤m 中 gcd(a,b) 的質因子個數（含重數）≤ P 的對數。

數學轉化

• 設 A(d) = #{gcd=a=d}, B(d) = #{d|gcd} = ⌊n/d⌋ * ⌊m/d⌋。
• 莫比烏斯反演：A(d) = ∑_{k≥1} μ(k) * B(d*k)。
• 答案 = ∑_{d: ω(d)≤P} A(d)，其中 ω(d) 為質因子個數（含重）。
• 交換求和序：∑_k μ(k) * ∑_{d: ω(d)≤P} B(d*k)。定義 F[k][c] = ∑_{d: ω(d)=c} μ(k) [條件]...

核心優化：塊狀處理 + 前綴和

1. 線性篩預計算 μ(i)、ω(i) (質因子個數)。
2. 構建 preMobi[i][c] = ∑_{j≤i, ω(j)≤c} μ(j) 的二維前綴和（c ≤ 19 因 2^19 > 5e5）。
3. 查詢時利用 ⌊n/i⌋ 只有 O(√n) 種取值，分塊求和：

for (int i=1; i<=n; i=ed+1) {
    ed = min(n/(n/i), m/(m/i));
    ans += (preMobi[ed][P] - preMobi[i-1][P]) * (n/i) * (m/i);
}

關鍵代碼

void getMobi() { /* 線性篩同時求 μ 和 ω */ }
void getpreMobi() {
    for (i=1; i
複雜度

預處理：O(N log N) ≈ 5e5 * log，一次性。
單查詢：O(√n) 塊數，極快支持 5000 組。

本題將「質因子個數限制」引入莫比烏斯反演，通過二維前綴和（質因子個數維 + 數值維）實現塊狀查詢，是數論高級技巧綜合運用的經典案例。