POJ 1845 Sumdiv：質因數分解與等比數列求和取模

POJ 1845 Sumdiv：Aᴮ 所有約數之和模 9901

數學推導

A = Π pᵢᵃⁱ，則 Aᴮ 所有約數之和為：

Sum = Π [1 + pᵢ + pᵢ² + ... + pᵢ^(aᵢ×B)]  (mod 9901)

等比數列快速求和（遞歸二分）

設 S(n) = 1 + p + p² + ... + pⁿ。

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

遞歸深度 O(log n)，配合快速冪求 p^k mod 9901。

核心代碼

const int MOD = 9901;
ll mod_pow(ll a, ll b) {
    ll r=1; while(b){ if(b&1) r=r*a%MOD; a=a*a%MOD; b>>=1; } return r;
}
ll geo_sum(ll p, ll n) { // 1 + p + ... + p^n
    if (n==0) return 1;
    if (n&1) return geo_sum(p, n/2) * (1 + mod_pow(p, n/2+1)) % MOD;
    else return (geo_sum(p, n/2-1) * (1 + mod_pow(p, n/2+1)) + mod_pow(p, n/2)) % MOD;
}
void factor(int n) { // 質因數分解
    for (int i=2; i*i<=n; i++) if (n%i==0) {
        p[cnt]=i; k[cnt]=0;
        while (n%i==0) { n/=i; k[cnt]++; }
        cnt++;
    }
    if (n>1) { p[cnt]=n; k[cnt]=1; cnt++; }
}
int main() {
    int a,b; scanf("%d%d",&a,&b);
    factor(a);
    ll ans=1;
    for (int i=0;i