Sumdiv

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1340 字

求A^B的所有正约数之和，结果对9901取模

一本通
例

正文

/*
原题：Sumdiv (POJ 1845 / Romania OI 2002)
题意：求 A^B 的所有正约数之和，结果对 9901 取模。
思路：对 A 质因数分解 A=∏p_i^{e_i}，则 A^B 的约数和 = ∏(1+p_i+...+p_i^{e_i*B})。
      等比数列求和用分治递归，天然规避 p_i≡1 (mod 9901) 时逆元不存在的问题。
复杂度：时间 O(√A · log B)，空间 O(1)。
易错点：模数 9901 为质数，当 p_i≡1 (mod 9901) 时不能用逆元，分治求和可正确处理；
      B=0 时答案为 1。
*/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=9901;
ll powmod(ll a, ll b){
    ll res=1%MOD;
    a%=MOD;
    while(b>0){
        if(b&1){
            res=res*a%MOD;
        }
        a=a*a%MOD;
        b>>=1;
    }
    return res;
}
// 求 1+p+p^2+...+p^c  (mod MOD)，分治避免除法/逆元
ll sum_geo(ll p, ll c){
    p%=MOD;
    if(c==0){
        return 1;
    }
    if(c%2==1){
        ll k=c/2;
        ll s=sum_geo(p, k);
        ll pk=powmod(p, k+1);
        return s*(1+pk)%MOD;
    }
    ll k=c/2;
    ll s1=sum_geo(p, k);
    ll s2=sum_geo(p, k-1);
    ll pk=powmod(p, k+1);
    return (s1+pk*s2)%MOD;
}
int main(){
    ll A, B;
    cin>>A>>B;
    if(B==0){
        cout<<1<<"\n";
        return 0;
    }
    ll ans=1;
    for(ll p=2; p*p<=A; p++){
        if(A%p==0){
            ll e=0;
            while(A%p==0){
                A/=p;
                e++;
            }
            ans=ans*sum_geo(p, e*B)%MOD;
        }
    }
    if(A>1){
        ans=ans*sum_geo(A, B)%MOD;
    }
    cout<<ans<<"\n";
    return 0;
}

Sumdiv

正文

一本通·提高篇的其它内容