约数个数定理

$$ \prod_{i=1}^{k} p_{i}^{a_{i}}=p_{1}^{a_{1}} \cdot p_{2}^{a_{2}} \cdots p_{k}^{a_{k}} $$

$$ f(n)=\prod_{i=1}^{k} a_{i}+1=\left(a_{1}+1\right)\left(a_{2}+1\right) \cdots\left(a_{k}+1\right) $$

约数之和定理
$$ \left(p_{1}^{0}+p_{1}^{1}+\ldots+p_{1}^{a_{1}}\right)\left(p_{2}^{0}+p_{2}^{1}+\ldots p_{2}^{a_{2}}\right) \ldots\left(p_{k}^{0}+p_{k}^{1}+\ldots p_{k}^{a k}\right) $$

如果$k$是偶数， 一共有奇数项：
$$ \operatorname{sum}(p, k) =p^{0}+p^{1} \cdot p^{k-1}+p^{k} \\ =p^{0}+p\left(p^{0}+\cdots+p^{k-2}+p^{k-1}\right) \\ $$

$$ =1+p \cdot \operatorname{sum}(p, k-1) $$

if (k % 2 == 0) return (1 + p % mod * sum(p, k - 1) ) % mod;

如果$k$是奇数， 一共有偶数项：
$$ \operatorname{sum}(p, k) =p^{0}+p^{1}+\cdots+p^{k} \\ $$
$$ =\left(p^{0}+\cdots+p^{k / 2}\right)+\left(p^{\left(\frac{k}{2}+1\right)}+\cdots+p^{k}\right) \\ =p^{0}+\cdots+p^{\frac{k}{2}}+p^{\frac{k}{2}} \cdot\left(p^{0}+\cdots+p^{\frac{k}{3}}\right) \\ $$
$$ =\left(1+p^{\left(\frac{k}{2}+1\right)}\right) \cdot \operatorname{sum}\left(p, \frac{k}{2}\right) $$

if (k % 2) return (1 + qmi(p, k / 2 + 1)) * sum(p, k / 2) % mod;

#include<iostream>

using namespace std;
const int mod = 9901;

int qmi(int a, int k) {
    int res = 1;
    a = a % mod;
    while (k) {
        if (k & 1) res = res * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res;
}

int sum(int p, int k) {
    if (k == 0) return 1;
    if (k % 2 == 0) return (1 + p % mod * sum(p, k - 1)) % mod;
    if (k % 2) return (1 + qmi(p, k / 2 + 1)) * sum(p, k / 2) % mod;
}

int main() {
    int a, b;
    cin >> a >> b;
    int res = 1;
    for (int i = 2; i <= a / i; i++) {
        if (a % i == 0) {
            int s = 0;
            while (a % i == 0) {
                a /= i, s++;
            }
            res = res * (sum(i, b * s)) % mod;
        }
    }

    if (a > 1) res = res * (sum(a, b)) % mod;
    if (a == 0) res = 0;

    cout << res;
}