本题关键就是如何分治求出$p^0 + \cdots + p^k = sum(p, k)$
当 k 为偶数时,共有奇数项:
$$ p^0 + \cdots + p^k = 1 + p * (p^0 + \cdots + p^{k - 1}) \\
= 1 + p * sum(p, k - 1)$$
当 k 为奇数时,共有偶数项
$$ p^0 + \cdots + p^k = p^0 + \cdots + p ^{ \frac k2 - 1} + p ^{ \frac k2} + p ^{ \frac k2 + 1} + \cdots + p ^ k \\
= (p^0 + \cdots + p ^{ \frac k2 - 1} + p ^{ \frac k2}) + (p ^{ \frac k2 + 1} + \cdots + p ^ k) \\ = (p^0 + \cdots + p ^{ \frac k2 - 1} + p ^{ \frac k2}) + p ^{ \frac k2 + 1}(p^0 + \cdots + p^{\frac k2}) \ 当k为奇数时 p ^{\lfloor \frac k2 \rfloor + 1} * p ^{\lfloor \frac k2 \rfloor} = p ^ k \\
= sum(p, k / 2) * (1 + p ^{\frac k2 + 1})$$
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int mod = 9901;
unordered_map<int, int> primes;
int pow(int a, int b){
int res = 1;
while(b){
if(b & 1) res = (LL) res * a % mod;
a = (LL) a * a % mod;
b >>= 1;
}
return res % mod;
}
void prime(int x){
for(int i = 2; i <= x / i; i ++){
while(x % i == 0){
primes[i] ++;
x /= i;
}
}
if(x > 1) primes[x] ++;
}
int sum(int p, int k){
if(k == 0)return 1;
if(k % 2 == 0) return (p % mod * sum(p, k - 1) + 1) % mod;
else return sum(p, k / 2) * (pow(p, k / 2 + 1) + 1) % mod;
}
int main()
{
int a , b , res = 1;
cin >> a >> b;
prime(a);
for(auto c : primes){
res = res * sum(c.first, c.second * b) % mod;
}
if(!a) res = 0;
cout << res << endl;
}