HDU 2521 反素數：預處理約數個數 + 區間查詢最大值

問題：多測試用例，每次給定區間 [m, n]，求區間內約數個數最多的數（若有多個取最小者）。n ≤ 5000。

預處理約數個數

利用質因數分解公式：N = p₁^e₁ * p₂^e₂ * ...，約數個數 d(N) = (e₁+1)(e₂+1)...。

對 1..5000 每個數分解質因數，計算 d[i]。

代碼實現

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
LL primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79};
int divisorCnt[5005];

void Precompute() {
    divisorCnt[1] = 1;
    for (int i = 2; i <= 5000; i++) {
        int x = i, cnt = 1;
        for (int j = 0; primes[j] * primes[j] <= x; j++) {
            int e = 0;
            while (x % primes[j] == 0) { x /= primes[j]; e++; }
            cnt *= (e + 1);
        }
        if (x > 1) cnt *= 2;
        divisorCnt[i] = cnt;
    }
}

int main() {
    Precompute();
    int T; cin >> T;
    while (T--) {
        int m, n; cin >> m >> n;
        int best = m;
        for (int i = m+1; i <= n; i++)
            if (divisorCnt[i] > divisorCnt[best]) best = i;
        cout << best << endl;
    }
    return 0;
}

複雜度

• 預處理：O(N √N) ≈ 5000 × 70，極快；
• 查詢：O(區間長度)，單次 ≤ 5000，多測試也足夠；
• 空間：O(5000)。