直接快速幂

基本思路

整体思路不再赘述

对除以(p-1)的处理，直接把模数9901变成9901*(p-1)，这样既保证快速幂不会炸，又保留了整除性

C++ 代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll ksm(ll a,ll b,ll m)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=(ans*a)%m;
        b>>=1;
        a=(a*a)%m;
    }
    return ans;
}
int minp(int x)
{
    for(int i=2;i<=sqrt(x);i++)
    {
        if(x%i==0)  return i;
    }
    return x;
}
int main()
{
    int a,b;
    cin>>a>>b;
    if(!a)
    {
        cout<<0;
        return 0;
    }
    ll lp=minp(a),p,cnt=0;//lp是上一个素因子，p是当前素因子，cnt是上一个素因子的指数
    ll ans=1;
    while(a>1)
    {
        p=minp(a);
        if(p!=lp)
        {
            //把快速幂的模数9901替换成9901*(lp-1)，这样能在保证快速幂不爆longlong的情况下维持整除性
            ans=ans*((ksm(lp,cnt*b+1,9901*(lp-1))+9901*(lp-1)-1)/(lp-1))%9901;
            lp=p;
            cnt=1;
        }
        else    cnt++;
        a/=p;
    }
    cout<<ans*((ksm(p,cnt*b+1,9901*(p-1))+9901*(p-1)-1)/(p-1))%9901;//最后一个素因子在while里面没算
    return 0;
}