POJ 1845 Sumdiv 求 A^B 因子和：數論與模運算結合

POJ 1845 Sumdiv：A^B 所有因子和模 9901

核心公式：若 N = p₁^e₁ p₂^e₂ ... pₖ^eₖ，則因子和 σ(N) = ∏ (pᵢ^(eᵢ+1)-1)/(pᵢ-1)。對於 A^B，指數變為 eᵢ×B。關鍵難點：模 9901 非質數，分母可能無逆元，需用遞歸/二分法計算等比數列和。

等比數列和模運算

求 S = 1 + p + p² + ... + p^n (mod M)。遞歸公式：

• n 為奇數：S = (1 + p^((n+1)/2)) × S((n-1)/2)
• n 為偶數：S = 1 + p × S(n-1)

或用二分遞歸：S(n) = S(n/2) × (1 + p^(n/2+1)) (n 奇) 等。

完整代碼框架

#include <cstdio> #include <iostream>
using namespace std; typedef long long LL;
const int MOD = 9901;

LL mod_pow(LL a, LL n) { // 快速冪
    LL r=1; while(n){ if(n&1) r=r*a%MOD; a=a*a%MOD; n>>=1; } return r;
}

LL geo_sum(LL p, LL n) { // 1+p+...+p^n mod MOD
    if (n==0) return 1;
    if (n%2) return (geo_sum(p, n-1)*p + 1) % MOD;
    return (geo_sum(p, n/2) * (1 + mod_pow(p, n/2+1))) % MOD;
}

int main() {
    LL A, B;
    while (cin >> A >> B) {
        // 分解質因數 A = ∏ p^e
        // 對每個 p，指數變為 e*B
        // ans = ∏ geo_sum(p, e*B) % MOD
        // 輸出 ans
    }
    return 0;
}

關鍵點

• 質因數分解 O(√A)，A ≤ 10⁹ 足夠。
• 模非質數時不可用費馬小定理求逆，必須用遞歸等比求和。
• 結果對 9901 取模。