我们知道约数之和的公式是$(p_1^0+p_1^1+p_1^2+p_1^{Bc1})(p_2^0+p_2^1+p_2^2+p_2^{Bc2})$.....
我们可以看出每一个式子都是等比数列
求出所有式子的乘积就是答案,那么每一项的和为$\frac{p_i^{Bc_i+1}-1}{p_i-1}$
$p_i^{Bc_i+1}$可以用快速幂求出来,但是我们不知道分母是不是能够整除分子,不能整除的话,可以会丢失精度
所以我们可以求$p_i-1$的逆元,因为9901是个质数,只要$p_i-1$不是9901的倍数,那么就可以用快速幂求出逆元
如果$p_i-1$是9901的倍数,不存在乘法逆元 那么$(p_i^0+p_i^1+p_i^2+p_i^{Bc_i})\equiv 1+1+1.....(mod)9901$
#include<bits/stdc++.h>
using namespace std;
const int N=1e5,mod=9901;
typedef long long ll;
typedef pair<int,int>PII;
PII p[N];
int cnt;
int qmi(ll a,ll n)
{
ll res=1;
while(n)
{
if(n&1) res=res*a%mod;
a=a*a%mod;
n>>=1;
}
return res;
}
int main()
{
ll a,b;
cin>>a>>b;
for(int i=2;i<=a/i;i++)
{
int s=0;
if(a%i==0)
{
while(a%i==0) s++,a/=i;
p[cnt++]={i,s};
}
}
if(a>1) p[cnt++]={a,1};
ll ans=1;
for(int i=0;i<cnt;i++)
{
ll x=p[i].first;
ll c=p[i].second;
if((x-1)%mod==0) ans=ans*(b*c+1)%mod;
else ans=ans*(qmi(x,b*c+1)-1+mod)%mod*qmi(x-1,mod-2)%mod; //(qmi(x,b*c+1)-1+mod) 加一个mod是为了防止出现负数
}
ans==cnt==0?0:ans; //a可能为0
cout<<ans<<endl;
return 0;
}