Chaser2 @ 2021-11-16 15:42:02
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =1e5+5, mod = 9901;
int p[N],s[N];
ll qpow(ll a, ll b)
{
ll res=1;
while(b)
{
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int main()
{
int a,b,cnt=0;
cin>>a>>b;
for(int i=2; i<=a/i; i++)
{
if(a%i==0)
{
p[++cnt]=i;
while(a%i==0)
{
s[cnt]++;
a/=i;
}
}
}
if(a>1)
{
p[++cnt]=a;
s[cnt]++;
}
ll ans=1;
for(int i=1; i<=cnt; i++)
{
//cout<<p[i]<<" "<<s[i]<<endl;
ans=(ans*(qpow(p[i],s[i]*b+1)-1+mod)%mod*qpow(p[i]-1,mod-2)%mod+mod)%mod;
}
cout<<(ans+mod)%mod<<endl;
system("pause");
return 0;
}
by Yansuan_HCl @ 2022-03-05 19:52:31
可能