XDU 1022 A simple math problem 2：數論篩法求前綴和

題目大意

定義 f(n) = Σ_{i=1..n} ⌊n/i⌋。求 sum(a,b) = Σ_{n=a..b} f(n) mod 1007。多組查詢（≤10000），a,b ≤ 1,000,000。

數學轉化

f(n) 等價於滿足 x*y ≤ n 的正整數對 (x,y) 的個數。定義 g(n) = 滿足 x*y = n 的對數（即 n 的約數個數）。則 f(n) = Σ_{k=1..n} g(k)，即 g 的前綴和。進而 sum(a,b) = Σ_{n=a..b} f(n) 是 f 的前綴和，即 g 的二階前綴和。

篩法預處理

1. 線性篩或埃氏篩求出所有 ≤ 1e6 的質數。
2. 初始化 g[i] = 0。對每個 i=1..1e6，對其倍數 j=i, 2i, ... 做 g[j]++。這等價於計算每個數的約數個數，複雜度 O(N log N)。
3. 計算 f[i] = (f[i-1] + g[i]) % MOD。
4. 計算 sum[i] = (sum[i-1] + f[i]) % MOD。
5. 查詢答案：(sum[b] - sum[a-1] + MOD) % MOD。

代碼實現

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAXN = 1000000;
const int MOD = 1007;

int g[MAXN+1];
int f[MAXN+1];
int sum[MAXN+1];

void init() {
    memset(g, 0, sizeof(g));
    for (int i = 1; i <= MAXN; i++)
        for (int j = i; j <= MAXN; j += i)
            g[j]++;
    for (int i = 1; i <= MAXN; i++) {
        f[i] = (f[i-1] + g[i]) % MOD;
        sum[i] = (sum[i-1] + f[i]) % MOD;
    }
}

int main() {
    init();
    int a, b;
    while (scanf("%d%d", &a, &b) == 2) {
        int ans = (sum[b] - sum[a-1] + MOD) % MOD;
        printf("%d\n", ans);
    }
    return 0;
}

複雜度分析

• 預處理：O(N log N) ≈ 1e6 * 14 ≈ 1.4e7 操作，極快。
• 查詢：O(1)。
• 空間：三個 int 數組約 12MB。

總結

本題核心是將 ⌊n/i⌋ 求和轉化為約數個數統計，利用篩法 O(N log N) 預處理所有 g(n)，再做兩次前綴和即可 O(1) 回答查詢。體現了「數論函數前綴和 + 篩法」的通用技巧。