POJ 1845 Sumdiv：算術基本定理求因子和模質數

問題描述

給定 n, m，求 S = σ(nᵐ) mod 9901，其中 σ 為因子和函數。n, m ≤ 10⁹，多測試用例。

數學基礎

若 n = Π pᵢᵃⁱ，則 nᵐ = Π pᵢᵃⁱᵐ。因子和為等比數列乘積：

σ(nᵐ) = Π (1 + pᵢ + pᵢ² + ... + pᵢᵃⁱᵐ) = Π (pᵢᵃⁱᵐ⁺¹ - 1) / (pᵢ - 1)

模質數除法：逆元法

9901 為質數。若 pᵢ ≠ 1 (mod 9901)，分母有逆元：(p-1)⁻¹ ≡ (p-1)⁹⁸⁹⁹ (mod 9901)（費馬小定理）。

若 pᵢ ≡ 1 (mod 9901)，分母模 9901 為 0，無逆元。此時等比數列和 = 項數 = aᵢm + 1，直接取模。

遞歸求和法（通用、無需逆元）

sum(p, e) = 1 + p + ... + pᵉ

• e 為偶數：sum(p, e) = (1 + p^{e/2+1}) × sum(p, e/2)
• e 為奇數：sum(p, e) = 1 + p × sum(p, e-1)
• 遞歸深度 O(log e)，每步模 9901

完整代碼（逆元法）

#include 
using namespace std;
using ll = long long;
const int MOD = 9901;

ll mod_pow(ll a, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

ll geo_sum_inv(ll p, ll e) {  // (p^{e+1}-1)/(p-1) mod MOD
    if (p % MOD == 1) return (e + 1) % MOD;
    ll num = (mod_pow(p, e + 1) - 1 + MOD) % MOD;
    ll den = (p - 1 + MOD) % MOD;
    ll inv = mod_pow(den, MOD - 2);  // 費馬小定理求逆元
    return num * inv % MOD;
}

ll geo_sum_rec(ll p, ll e) {  // 遞歸法
    if (e == 0) return 1;
    if (e % 2 == 0) {
        ll half = geo_sum_rec(p, e / 2);
        ll term = mod_pow(p, e / 2 + 1);
        return (1 + term) % MOD * half % MOD;
    }
    return (1 + p % MOD * geo_sum_rec(p, e - 1)) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n, m;
    while (cin >> n >> m) {
        if (n == 0 && m == 0) break;
        ll ans = 1;
        ll tmp = n;
        for (ll p = 2; p * p <= tmp; ++p) {
            if (tmp % p == 0) {
                int cnt = 0;
                while (tmp % p == 0) { tmp /= p; ++cnt; }
                ans = ans * geo_sum_rec(p, cnt * m) % MOD;
            }
        }
        if (tmp > 1) ans = ans * geo_sum_rec(tmp, m) % MOD;
        cout << ans << '\n';
    }
    return 0;
}

關鍵點總結

複雜度

• 分解質因數：O(√n) ≈ 3×10⁴
• 快速冪/遞歸：O(log m) 每質因數
• 總體極快，適合大量測試用例