BZOJ 2154 Crash 的數字表格：莫比烏斯反演求 LCM 和

問題描述

給定 N, M（≤ 10⁷），構建 N×M 表格，第 (i, j) 格填 LCM(i, j)。求所有格子數值之和模 20101009。

數學轉化

LCM(i, j) = i * j / gcd(i, j)。令 g = gcd(i, j)，i = g * a, j = g * b，其中 gcd(a, b) = 1。則 LCM = g * a * b。

原式 ∑_{i=1}^N ∑_{j=1}^M LCM(i, j) = ∑_{g=1}^{min(N,M)} g * ∑_{a=1}^{N/g} ∑_{b=1}^{M/g} [gcd(a,b)=1] * a * b

莫比烏斯反演

利用恆等式 [gcd(a,b)=1] = ∑_{d|gcd(a,b)} μ(d)。交換求和順序：

內層和 = ∑_{d=1}^{min(N/g, M/g)} μ(d) * d² * (∑_{a'=1}^{N/(gd)} a') * (∑_{b'=1}^{M/(gd)} b')

其中 ∑_{k=1}^x k = x(x+1)/2。

整體公式

Ans = ∑_{g=1}^{min(N,M)} g * ∑_{d=1}^{min(N/g, M/g)} μ(d) * d² * S(N/(gd)) * S(M/(gd))

令 t = g * d，換元：Ans = ∑_{t=1}^{min(N,M)} S(N/t) * S(M/t) * ∑_{d|t} μ(d) * d² * (t/d)

定義 f(t) = ∑_{d|t} μ(d) * d² * (t/d) = t * ∑_{d|t} μ(d) * d。預計算 f(t) 前綴和，利用整除分塊技巧 O(√n) 求解。

代碼實現要點

• 線性篩法預計算 μ(n) 及前綴和 sum[i] = ∑_{k=1}^i k² μ(k) mod MOD。
• get(x, y) 計算 S(x) * S(y) mod MOD。
• calc(n, m) 整除分塊求 ∑_{i=1}^{min(n,m)} (sum[pos]-sum[i-1]) * get(n/i, m/i)。
• 主循環再次分塊：Ans = ∑ (i+pos)*(pos-i+1)/2 * calc(n/i, m/i)。

複雜度

預處理 O(N)，N=10⁷ 可行（~0.5s）。每次查詢 O(√N)，單測極快。內存 ~120MB（幾個 int 數組），符合 259MB 限制。

總結

本題是數論經典：LCM 求和 → gcd 分解 → 莫比烏斯反演 → 整除分塊優化。展示了從數學推導到工程實現的完整鏈路，是高難度數論題的優秀範例。