BZOJ 1257 [CQOI2007] 余數之和 解題報告：數論分塊 + 等差數列求和

問題描述

計算 J(n, k) = Σ_{i=1..n} (k mod i)。n, k ≤ 10^9，需 O(√k) 算法。

數學轉化

k mod i = k - i * ⌊k/i⌋。若 n > k，對於 i > k，k mod i = k，直接加 (n-k)*k，再處理 i=1..k。令 n = min(n, k)。

分塊技巧

⌊k/i⌋ 只有 O(√k) 種不同取值。對於相同商 q = ⌊k/i⌋ 的連續區間 [L, R]，余數形成等差數列：

k mod i = k - q*i  (i 從 L 到 R 遞減 q)
首項 = k - q*L, 末項 = k - q*R, 項數 = R-L+1
區間和 = (首項+末項)*項數/2 = (2k - q(L+R))*(R-L+1)/2

二分查找區間右端點

給定當前 L 和商 q，最大 R 滿足 ⌊k/R⌋ = q。二分 R ∈ [L, n]。

完整代碼

typedef long long ll;
ll n, k, ans;

ll findR(ll L, ll q) { // 找最大 R 使 k/R == q
    ll l = L, r = n;
    while (l < r) {
        ll mid = (l + r + 1) >> 1;
        if (k / mid == q) l = mid;
        else r = mid - 1;
    }
    return l;
}

int main() {
    scanf("%lld%lld", &n, &k);
    if (n > k) { ans += (n - k) * k; n = k; }
    ll L = 1;
    while (L <= n) {
        ll q = k / L;
        ll R = findR(L, q);
        ans += (2*k - q*(L+R)) * (R - L + 1) / 2;
        L = R + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

複雜度

• 循環次數 = 不同商的數量 = O(√k)。
• 每次二分 O(log n)，總體 O(√k log k)，k=10^9 约 6萬次操作，極快。

關鍵點

• 利用 k mod i = k - i*⌊k/i⌋ 轉化為商的分塊求和。
• 商相同區間內余數為等差數列，套用求和公式。
• 二分查找區間右端點，避免線性掃描。