考虑直接模拟,有 $A = p_1^{c_1} \cdot p_2^{c_2} \cdots p_n^{c_n}$,由此易得 $A^B = p_1^{Bc_1} \cdot p_2^{Bc_2} \cdots p_n^{Bc_n}$
由乘法分配律易得 $A^B$ 的所有约数之和为:
$$ S = (1 + p_1 + \cdot + p_{1}^{Bc_1}) \cdot (1 + p_2 + \cdot + p_{2}^{Bc_2}) \cdots (1 + p_n + \cdot + p_{n}^{Bc_n}) $$
如果直接模拟这个过程,根据公式去求解 $S$,直接迭代求,显然复杂度会爆掉
易想到的一个优化是对每一个括号用等比数列求和公式,但是公式中有除法,在模运算下做等效除法需要求逆元
不过本题的模数 $9901$ 是质数,可以用 费马小定理 结合 快速幂 求逆元,否则就要用 BSGS 了
不妨换一种思路考虑本题,采用 分治 的思想来求解 $\mathrm{sum}(p, c) = 1 + p + \cdots + p^c$,不妨设 $c$ 为奇数,则
$$ \begin{aligned} \mathrm{sum}(p, c) &= (1 + \cdots + p^{\frac{c-1}{2}}) +(p^{\frac{c+1}{2}} + \cdots + p^c) \\\\ &= \mathrm{sum}(p, \frac{c-1}{2}) + p^{\frac{c+1}{2}} \cdot \mathrm{sum}(p, \frac{c-1}{2}) \\\\ &= \mathrm{sum}(p, \frac{c-1}{2}) \cdot (1 + p^{\frac{c+1}{2}}) \\\\ \mathrm{sum}(p, c + 1) &= \mathrm{sum}(p, c) + p^{c+1} \end{aligned} $$
状态空间 的 问题边界 为 $\mathrm{sum}(p, 0) = 1$
利用该分治思想,求解本问题
#include <cstdio>
const int mod = 9901;
typedef long long LL;
int qmi(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;
}
int sum(int p, int k) {
if (k == 1) return 1;
if (k & 1) return (qmi(p, k - 1) + sum(p, k - 1)) % mod;
return (1 + qmi(p, k / 2)) * sum(p, k / 2) % mod;
}
int main() {
int a, b;
scanf("%d%d", &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 = (LL) res * sum(i, b * s + 1) % mod;
}
}
if (a > 1) res = (LL) res * sum(a, b + 1) % mod;
if (a == 0) res = 0;
printf("%d\n", res);
return 0;
}
if (a > 1) res = (LL) res * sum(a, b + 1) % mod;
if (a == 0) res = 0;这两步没看懂
a==0 表示的是输入的a的值为0 那res肯定为0
在求出所有小于sqrt(a)的质因子后 a还>1 说明 还有一个大于sqrt(a)的因子