POJ 1845 Sumdiv：A^B 約數和模 9901（遞歸等比數列求和 + 逆元避坑）

核心公式

A = ∏ p_i^a_i → A^B = ∏ p_i^a_iB。
約數和 σ = ∏ (p^e+1−1) / (p−1)。

除法陷阱與解決

模 9901 非質數（9901 = 99×100+1 = 9901，實為質數？驗證：9901 = 99×100+1，√9901≈99.5，試除 7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97 均不整除 → 9901 是質數）。
但 (p−1) 可能與 9901 不互質（如 p=2 → 分母 1 安全；p=3 → 分母 2 安全；但 p=9902 不可能因 p≤50000000）。實際上 p 為質因子，p−1 < 9901 通常互質，**但為避免逆元不存在，改用等比數列遞歸求和，完全避開除法**。

等比數列快速求和 S(k) = 1 + p + p² + … + pᵏ

• k 偶數：S(k) = (1 + p^k/2+1) × S(k/2−1) + p^k/2
• k 奇數：S(k) = (1 + p^k/2+1) × S(k/2)
• 遞歸出口 k=0 → 1。

配合快速冪計算 p^e mod 9901，時間 O(log k)。

代碼

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int MOD = 9901;

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

// 返回 1 + p + ... + p^n (mod MOD)
int64 geo_sum(int64 p, int64 n) {
    if (n == 0) return 1;
    if (n & 1) {
        int64 half = n / 2;
        return (1 + mod_pow(p, half + 1)) * geo_sum(p, half) % MOD;
    } else {
        int64 half = n / 2;
        return ((1 + mod_pow(p, half + 1)) * geo_sum(p, half - 1) % MOD + mod_pow(p, half)) % MOD;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int64 A, B;
    while (cin >> A >> B) {
        if (A == 0) { cout << 0 << '\n'; continue; }
        if (A == 1 || B == 0) { cout << 1 << '\n'; continue; }
        int64 ans = 1;
        int64 a = A;
        for (int64 p = 2; p * p <= a; ++p) {
            if (a % p) continue;
            int64 cnt = 0;
            while (a % p == 0) { a /= p; cnt++; }
            ans = ans * geo_sum(p, cnt * B) % MOD;
        }
        if (a > 1) ans = ans * geo_sum(a, B) % MOD;
        cout << ans << '\n';
    }
    return 0;
}

關鍵優勢

無需求模逆元，完全規避分母與模數不互質導致的逆元不存在問題，代碼更穩健。