题意：求$A^{B}$的所有约数之和$mod\ 9901$
思路：由结论有，一个数$n$进行质因数分解得到$n={p_{1}}^{c_{1}} * {p_{2}}^{c_{2}} *...* {p_{k}}^{c_{k}}$，那么$n$的约数之和为
$$sum=(1+{p_{1}}^{1}+\cdots+{p_{1}}^{c_{1}})*(1+{p_{2}}^{1}+\cdots +{p_{2}}^{c_{2}})*\cdots*(1+{p_{k}}^{1}+\cdots+{p_{k}}^{c_{k}})$$
所以对$A$质因数分解后，那么$A^{B}$的约数之和
$$sum=(1+{p_{1}}^{1}+\cdots+{p_{1}}^{B*c_{1}})*(1+{p_{2}}^{1}+\cdots +{p_{2}}^{B*c_{2}})*\cdots*(1+{p_{k}}^{1}+\cdots+{p_{k}}^{B*c_{k}})$$
上式中每个括号内都是等比数列，利用分治法对等比数列求和，设$sum(p，c)=1+p+p^2+\cdots+p^{c}$
当$c$为奇数时
$$sum(p,c)=(1+p+\cdots+p^{\frac{c-1}{2}})+(p^{\frac{c+1}{2}}+\cdots+p^c)=(1+p^{\frac{c+1}{2}})*sum(p,\frac{c-1}{2})$$
当$c$为偶数时
$$sum(p,c)=(1+p+\cdots+p^{\frac{c}{2}-1})+(p^{\frac{c}{2}}+p^{\frac{c}{2}+1}\cdots+p^{c-1})+p^c=(1+p^{\frac{c}{2}})*sum(p,\frac{c}{2}-1)+p^c$$
当$c$等于$0$，结束递归， 返回$1$即可
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath> using namespace std; typedef long long ll; const int N = ;
const ll mod = ; ll a, b;
ll p[N], c[N], m; void divide(ll n)
{
m = ;
for (ll i = ; i <= sqrt(n); i++) {
if ( == n % i) {
p[++m] = i, c[m] = ;
while ( == n % i) n /= i, c[m]++;
}
}
if (n > ) p[++m] = n, c[m] = ;
return;
} ll power(ll a, ll b, ll p)
{
ll res = ;
while (b) {
if (b & ) res = (res * a) % p;
a = (a * a) % p, b >>= ;
}
return res % p;
} ll sum(ll p, ll c)
{
if ( == c) return ;
if ( == c % ) {
ll tp1 = ( + power(p, (c + ) / , mod)) % mod;
ll tp2 = sum(p, (c - ) / ) % mod;
return tp1 * tp2 % mod;
}
else {
ll tp1 = ( + power(p, c / , mod)) % mod;
ll tp2 = sum(p, c / - ) % mod;
return (tp1 * tp2 % mod + power(p, c, mod)) % mod;
}
} int main()
{
scanf("%lld%lld", &a, &b);
divide(a);
if ( == a) printf("0\n");
else {
ll res = ;
for (int i = ; i <= m; i++)
res = res * sum(p[i], b * c[i]) % mod;
printf("%lld\n", res);
}
return ;
}