传送门
显然需要先求出ab" role="presentation" style="position: relative;">abab的所有质因数和它们的指数。
但求出来之后并不能直接上等比数列求和公式。
因为这道题并不能直接求逆元。
原因?
a的某个因数有可能已经大于9901了。
于是它可能是9901的倍数。
这样就gg了。
于是我们可以二分求解等比数列的和。
代码:
#include<iostream>
#include<cmath>
#define mod 9901
#define ll long long
#define xx first
#define yy second
using namespace std;
int a,b,tot=0;
ll ans=1;
inline ll ksm(ll x,ll p){
ll ret=1;
while(p){
if(p&1)ret=ret*x%mod;
x=x*x%mod,p>>=1;
}
return ret;
}
inline ll calc(ll x,ll y){
if(!y)return 1;
if(y&1)return ((1+ksm(x,y/2+1))*calc(x,y/2))%mod;
return ((1+ksm(x,y/2+1))*calc(x,y/2-1)+ksm(x,y/2))%mod;
}
int main(){
cin>>a>>b;
for(int i=2;i*i<=a;++i){
int cnt=0;
while(a%i==0)a/=i,++cnt;
(ans*=calc(i,cnt*b))%=mod;
}
if(a-1)(ans*=calc(a,b))%=mod;
cout<<ans;
return 0;
}