$ N = {p_1}^{a_1} * {p_2}^{a_2} * .... * {p_n}^{a_n} $
$约数个数: (a_1+1) * (a_2+1) * … * (a_n+1) $
$约数之和: (1+p_1+{p_1}^2+…+{p_1}^{a_1})(1+p_2+{p_2}^2+…+{p_2}^{a_2})…(1+p_n+{p_n}^2+…+{p_n}^{a_n}) $
本题其实就是求约数之和,但因为模数太小,会卡费马小定理,所以不能直接用等比数列求和公式。
我们设
$S_n=1+p+p^2+…+p^{n-1}$
$S_n-1=p+p^2+…+p^{n-1}$
$S_1=1$
那么
$S_{2n}=1+p+p^2+…+p^{n-1}+p^n+p^{n+1}+…+p^{2n-1}$
在后 $n$ 项中提出 $p^n$
$S_{2n}=1+p+p^2+…+p^{n-1}+p^n*(1+p+p^2+…+p^{n-1})$
$S_{2n}=(p^n+1)*(1+p+p^2+…+p^{n-1})$
$S_{2n}=(p^n+1)*(S_n)$
$S_{2n+1}=1+p+p^2+…+p^n+p^{n+1}+p^{n+2}+…+p^{2n}$
在后$n$项中提出$p^n$
$S_{2n+1}=1+p+p^2+…+p^n+(p^n)*(p+p^2+..+p^n)$
$S_{2n+1}=S_{n+1}+(p^n) * (S_{n+1}-1)$
又因为 $2n$ 一定为偶数, $2n+1$ 一定为奇数,所以我们可以分成 $n$ 为奇数和偶数两种情况递归求解$S_n$
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
using namespace std;
const int mod=9901;
typedef long long LL;
map<int,int> mp;
int qpow(int a,int b){
int res=1;
while(b){
if(b&1) res=1LL*res*a%mod;
a=1LL*a*a%mod;
b>>=1;
}
return res;
}
//分解质因数
void get_primes(int a){
for(int i=2;i*i<=a;++i){
while(a%i==0){
mp[i]++;
a/=i;
}
}
if(a>1) mp[a]++;
}
//计算S_n
int S(int p,int n){
if(n==1) return 1;
if(n&1) return (S(p,(n+1)/2)+1LL*qpow(p,n/2)*(S(p,(n+1)/2)-1)%mod)%mod;
return 1LL*(qpow(p,n/2)+1)*S(p,n/2)%mod;
}
void solve(int a,int b){
get_primes(a);
int res=1;
for(auto s:mp){
int p=s.first,n=s.second;
res=1LL*res*S(p,n*b+1)%mod;
}
cout<<res<<"\n";
}
int main(){
int a,b;
cin>>a>>b;
if(a==0) puts("0");
else if(b==0) puts("1");
else solve(a,b);
return 0;
}