NYOJ 508 余數求和：√n 分塊優化計算 Σ(n%i) 與 Σ(k%i)

問題描述

給 n, k (≤10⁹)，求 S = Σ_{i=1}^{n} (k % i)。多行輸入直到 EOF。

核心觀察：商相同的區間

對固定 k，k / i 只有 O(√k) 種不同取值。
對於給定商 q = k / i，i 的取值範圍為 [k/(q+1)+1, k/q]。
在該區間內，k % i = k - q * i，求和可用等差數列公式。
遍歷所有 q，累加區間和，總時間 O(√k)。

算法流程

1. 計算 sum_mod(k, n) = Σ_{i=1}^{min(n,k)} (k % i)。
     若 n > k，額外部分 Σ_{i=k+1}^{n} (k % i) = Σ_{i=k+1}^{n} k = k * (n - k)。
2. 對 i = 1 開始，當 i ≤ min(n,k)：
     q = k / i;
     next_i = k / q + 1; // 區間右端點 + 1
     區間 [i, min(next_i-1, n)] 內商均為 q。
     區間和 = q * (i + last) * cnt / 2 其中 cnt = last - i + 1，但實際 k % i = k - q*i，所以區間和 = cnt * k - q * (i + last) * cnt / 2。
     i = next_i。

代碼實現 (C++)

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int64 sum_mod(int64 k, int64 n) {
    if (n <= 0) return 0;
    int64 limit = min(n, k);
    int64 res = 0;
    for (int64 i = 1, last; i <= limit; i = last + 1) {
        int64 q = k / i;
        last = min(limit, q ? k / q : limit);
        int64 cnt = last - i + 1;
        // Σ (k - q*j) for j=i..last = cnt*k - q * (i+last)*cnt/2
        res += cnt * k - q * (i + last) * cnt / 2;
    }
    if (n > k) res += k * (n - k); // i > k 時 k%i = k
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int64 n, k;
    while (cin >> n >> k) {
        cout << sum_mod(k, n) << '\n';
    }
    return 0;
}

複雜度

• 時間：O(√k) 每查詢，k ≤ 10⁹ 時 √k ≈ 31623，極快。
• 空間：O(1)。

關鍵點

• 利用除法商取值少、區間連續的性質分塊求和。
• 區間和用等差數列公式 O(1) 計算。
• 處理 n > k 情況：i > k 時餘數恆為 k。

這是「除法分塊」的經典應用，將 O(n) 求和優化為 O(√n)，廣泛用於數論求和問題。