简约
首先需要知道一些基本的数学知识（算数基本定理之类的）
然后推导公式，发现是个等比数列求和，但因为要取模，所以套公式很麻烦。
进行优化，可以用递归来模拟公式，相当于二分计算（奇数的话，留出末项，把前面二分计算，最后乘积）
具体推导过程见图片。
推导过程
代码
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int mod = 9901;
int n, m, ans = 1;
int qp(int x, int y)
{
int res = 1;
x %= mod;
while(y)
{
if(y & 1) res = (res * x) % mod;
x = (x * x) % mod;
y >>= 1;
}
return res % mod;
}
int sum(int p, int k)
{
if(!k) return 1;
if(k & 1) return ((1 + qp(p, k / 2 + 1)) * sum(p, k / 2)) % mod;
return ((p % mod) * sum(p, k - 1) + 1) % mod;
}
int main()
{
ios :: sync_with_stdio(0);
cin >> n >> m;
for(int i = 2; i <= n; ++i)
{
int tot = 0;
while(n % i == 0)
{
tot++;
n /= i;
}
if(tot) ans = (ans * sum(i, tot * m)) % mod;
}
if(!n) puts("0");
else cout << ans << endl;
return 0;
}
2020 RP++
