测试链接：约数之和
求 \(A^B\) 的所有约数之和 \(S \bmod 9901\) 的值。
根据算术基本定理，每个正整数可以被唯一分解为若干质因数的幂的乘积，那么：
\[A=p_{1}^{a_{1}} \times p_{2}^{a_{2}} \times \dots \times p_{k}^{a_{k}}
\]
因此：
\[A^B=p_{1}^{B\cdot a_{1}} \times p_{2}^{B\cdot a_{2}} \times \dots \times p_{k}^{B\cdot a_{k}}
\]
又由于约数和定理，那么 \(A^B\) 的约数和可以被写成：
\[(1+p_{1}^1+p_{1}^{2}+\dots p_{1}^{B\cdot a_{1}})(1+p_{2}^1+p_{2}^{2}+\dots p_{2}^{B\cdot a_{2}})\dots (1+p_{1}^1+p_{1}^{2}+\dots p_{k}^{B\cdot a_{k}})
\]
不难发现，每个括号都是一个关于某个质因数的等比数列。但由于等比数列求和需要做除法，而计算过程中需要 \(\bmod 9901\)，于是我们考虑通过分治求等比数列和。
设 \(\sum(p,c)=1+p^0+p^1+\dots p^{c}\)：
- 若 \(c\) 为奇数，则：
\[\sum(p,c)=\left( 1+p^0+p^1+\dots +p^{\frac{c-1}{2}} \right)+\left( p^{\frac{c+1}{2}}+p^{\frac{c+1}{2}+1}+\dots+p^c \right)=\left( 1+p^1+p^2+\dots+p^{\frac{c-1}{2}} \right)+p^{\frac{c+1}{2}}\left( 1+p^1+p^2+\dots+p^{\frac{c-1}{2}} \right)=\sum\left( p, \frac{{c-1}}{2} \right)\left( 1+p^\frac{{c+1}}{2} \right)
\]
- 若 \(c\) 为偶数，则：
\[\sum(p,c)=\sum\left( p, \frac{c}{2}-1 \right)\left( 1+p^\frac{c}{2} \right) +p^c
\]
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int mod = 9901;int qmi(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;
}int sum(int p, int c) {if (c == 0) return 1;if (c % 2) return sum(p, (c - 1) / 2) * (1 + qmi(p, (c + 1) / 2)) % mod;return sum(p, c / 2 - 1) * (1 + qmi(p, c / 2)) % mod + qmi(p, c) % mod;
}int main() {int A, B;cin >> A >> B;if (A == 0) {cout << 0;return 0;}unordered_map<int, int> prs;int x = A;for (int i = 2; i <= x / i; i ++) {while (x % i == 0) {prs[i] ++;x /= i;}}if (x > 1) prs[x] ++;int ans = 1;for (auto& [p, c] : prs) {ans = ans * sum(p, c * B) % mod;}cout << ans;return 0;
}