题目描述

求A^B的所有约数之和mod 9901 (1<=A, B<=5*10^7)。

输入

输入A, B

输出

输出答案

样例输入

2 3

样例输出

15

【样例说明】

2^3=8，约数有1,2,4,8，和为15

【数据规模和约定】

20%数据 1<=A, B<=50
40%数据 1<=A, B<=5000
另有20%的数据 A为素数
100%数据 (1<=A, B<=5*10^7

思路

可以先将A分解质因数,$A=P_1^{C_1}*P_2^{C_2}*…P_m^{C_m}$
$A^B=P_1^{C_1*B}*P_2^{C_2*B}\…*P_m^{C_m*B}$
因此,所有约数和为$(1+P_1^1+P_1^2+…+P_1^{C_1*B})*…(1+P_m^1+P_m^2+…+P_m^{C_mB})$
用求幂累加和里的方式即可快速算出
在分解质因数时,质数只需预处理到SQRT(A)

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int a,b,num,cnt;
ll k=9901;

struct node{
    int num,k;
}t[7100];

bool IsPrime[7100];
int Prim[7100];
void euler_prime(int n){
    int j;
    for(int i=2;i<=n;i++){
        if(!IsPrime[i])
            Prim[++num]=i;
        for(j=1;j<=num;j++){
            if(i*Prim[j]>n)
                break;
            IsPrime[i*Prim[j]]=1;
            if(i%Prim[j] == 0)
                break;
        }
    }
}

ll po(ll b,ll n){
    ll ans=1,t=b%k;
    while (n){
        if (n&1){
            ans=(ans*t)%k;
        }
        t=(t*t)%k;
        n>>=1;
    }
    return ans;
}

ll add(ll b,ll r){
    if (r==1) return b%k;
    if (r&1){
        return (po(b,r)+add(b,r-1))%k;
    }else{
        return ((1+po(b,r/2))*add(b,r/2))%k;
    }
}

int main(){
    cin>>a>>b;
    euler_prime(sqrt(a));
    for (int i=1;i<=num;++i){
        if (a%Prim[i]==0){
            int tt=0;
            while (a%Prim[i]==0){
                tt++;
                a/=Prim[i];
            }
            t[++cnt].k=Prim[i];
            t[cnt].num=tt;
        }
    }
    if (a!=1) t[++cnt].k=a,t[cnt].num=1;
    ll ans=1;
    for (int i=1;i<=cnt;++i){
        ll tmp=add(t[i].k,(ll)t[i].num*b)+1;
        ans=(ans*tmp)%k;
    }
    cout<<ans<<endl;
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/55/