UVa 294 Divisors：區間內最大約數個數（質因數分解 + 篩法）

問題描述

多組查詢，每組給定 [a,b] (1≤a≤b≤1e9, b-a≤1e4? 實際無明確限制但需高效)，找區間內約數個數最多的數（若多個取最小），輸出該數及約數個數。

約數個數公式

若 n = ∏ p_i^e_i，則約數數 d(n) = ∏ (e_i + 1)。
質因數分解後直接計算。

篩法預計算質數

b ≤ 1e9 ⇒ √b ≤ 31623。篩出 34000 以內所有質數（約 3600 個）。

分解函數

int divisorCount(int x, const vector& primes) {
    int cnt = 1;
    for (int p : primes) {
        if (1LL*p*p > x) break;
        if (x % p == 0) {
            int e = 0;
            while (x % p == 0) { x /= p; ++e; }
            cnt *= (e + 1);
        }
    }
    if (x > 1) cnt *= 2; // 剩餘質因子
    return cnt;
}

主循環

int main() {
    vector primes; sieve(primes, 34000);
    int T; cin >> T;
    while (T--) {
        int a,b; cin>>a>>b;
        int bestNum = a, bestDiv = 0;
        for (int i=a;i<=b;++i) {
            int d = divisorCount(i, primes);
            if (d > bestDiv) { bestDiv = d; bestNum = i; }
        }
        cout << "Between " << a << " and " << b << ", " << bestNum
             << " has a maximum of " << bestDiv << " divisors.\n";
    }
}

優化技巧

• 區間篩法：對 [a,b] 同時分解，類似線性篩，但實現較複雜。
• 緩存質因數分解結果（若有重複查詢）。
• 提前剪枝：若剩餘區間長度 × 最大可能約數增長 < 當前最佳，可剪枝（難估計）。

複雜度

每數分解 O(√n / log n)，區間長 L 總 O(L √b / log b)。L ≤ 1e4 時可接受。