数学：洛谷P1593 因子和

原题传送门

a=p1^k1???p2^k2???p3^k3???…?pn^kn??
ab=p1^k1??b??p2^k2??b??p3^k3??b??…?pn^kn??b?
ans=(1+p1¹?+p1²?+p1³?+…+p1^k1??b?)?(1+p2¹?+p2²?+p2^3?+…+p1^k2??b?)?...?(1+pn¹?+pn²?+pn³?+…+pn^kn??b?)

然后用等比数列求和公式+快速幂求得

#include
#define N 50000007
#define mod 9901
using namespace std;
int main(){
    int a,b,n,i,j,x,s,ans,mi[10004],fac[10004];
    cin>>a>>b;
    b%=(mod-1);n=0;
    for(i=2;i<=a;i++){
        if(a%i==0) n++;
        while(a%i==0){
            fac[n]=i;
            mi[n]++;
            a/=i;
        }
    }
    for(i=1;i<=n;i++){mi[i]*=b;mi[i]%=(mod-1);}
    ans=1;
//    cout<
    for(i=1;i<=n;i++){
        x=1;s=1;
        for(j=1;j<=mi[i];j++){
            x*=(fac[i]%mod);x%=mod;
            s+=x;s%=mod;
        }
//        cout<
        ans*=s;ans%=mod;
    }
    cout<<ans;
    return 0;
}