1633：【例 3】Sumdiv

题目描述

求 $A^B$ 的所有约数之和 $\bmod 9901$。

输入格式

输入两个整数 $A,B$。

输出格式

输出答案 $\bmod 9901$。

样例

样例输入 #1

2 3

样例输出 #1

15

样例解释 #1

$2^3 = 8$，$8$ 的所有约数为 $1,2,4,8$，$1+2+4+8=15$，$15 \bmod 9901 = 15$，因此输出 $15$。

数据范围

对于全部数据，$0 \le A,B \le 5 \times 10^7$。

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题需要计算 $A^B$ 的所有约数之和。设 $A$ 的质因数分解为 $A = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$，则 $A^B = p_1^{a_1 B} p_2^{a_2 B} \cdots p_k^{a_k B}$。$A^B$ 的约数之和为：

$$\sigma(A^B) = \prod_{i=1}^k (1 + p_i + p_i^2 + \cdots + p_i^{a_i B}) = \prod_{i=1}^k \frac{p_i^{a_i B + 1} - 1}{p_i - 1}$$

因此，我们需要对 $A$ 分解质因数，然后对每个质因子 $p_i$ 计算 $\frac{p_i^{a_i B + 1} - 1}{p_i - 1} \bmod 9901$，最后将所有结果相乘再取模。

由于 $A,B$ 可能很大，直接计算 $p_i^{a_i B + 1}$ 会溢出，需要使用快速幂取模。但分母 $p_i - 1$ 可能不是 $9901$ 的倍数，需要求其模 $9901$ 下的逆元（因为 $9901$ 是质数，可以用费马小定理求逆元）。注意：如果 $p_i \equiv 1 \pmod{9901}$，则 $p_i - 1$ 是 $9901$ 的倍数，此时公式 $\frac{p_i^{a_i B + 1} - 1}{p_i - 1}$ 在模 $9901$ 下不能直接除，需要特殊处理。此时 $p_i \equiv 1 \pmod{9901}$，所以 $1 + p_i + p_i^2 + \cdots + p_i^{a_i B} \equiv 1 + 1 + 1 + \cdots + 1 = a_i B + 1 \pmod{9901}$。因此，在这种情况下，该因子的贡献为 $a_i B + 1 \bmod 9901$。

算法步骤：

1. 对 $A$ 分解质因数（$A \le 5\times 10^7$，可以用试除法，枚举到 $\sqrt{A}$）。
2. 对于每个质因子 $p$ 及其指数 $a$，计算 $t = a \times B$。
3. 如果 $p \bmod 9901 == 1$，则贡献 $= (t + 1) \bmod 9901$。
4. 否则，贡献 $= \frac{(p^{t+1} \bmod 9901 - 1 + 9901) \bmod 9901 \times \text{inv}(p-1) \bmod 9901$，其中 $\text{inv}(p-1)$ 是 $p-1$ 模 $9901$ 的逆元（可用费马小定理：$inv = (p-1)^{9901-2} \bmod 9901$）。
5. 将所有贡献相乘取模 $9901$。

注意：$A$ 可能为 $0$ 或 $1$。如果 $A=0$，则 $A^B=0$（$B>0$）或 $1$（$B=0$）。但 $0$ 的约数之和通常定义为 $0$？实际上，$0$ 有无限个约数，但题目中 $A,B$ 是非负整数，$A=0$ 时需要特判：

• 如果 $B=0$，则 $0^0$ 无定义，但题目可能保证 $A,B$ 不同时为 $0$？数据范围 $0 \le A,B$，可能同时为 $0$。根据约定，通常 $0^0$ 未定义，但题目可能规避。为安全起见，特判：如果 $A=0$，输出 $0$（因为 $0^B=0$（$B>0$），其约数之和可以认为是 $0$；如果 $B=0$ 且 $A=0$，输出 $1$？但题目没有明确，根据样例可能不会出现）。实际上，$A=0$ 且 $B>0$ 时，$A^B=0$，其约数之和为 $0$（因为 $0$ 没有正约数？但 $0$ 可以被任何非零数整除，所以约数个数无限，但约数之和发散？在数论中通常不考虑 $0$ 的约数之和）。题目可能保证 $A>0$？数据范围包括 $0$，但实际测试可能 $A>0$。为保险，特判：如果 $A=0$，输出 $0$。

如果 $A=1$，则 $A^B=1$，约数之和为 $1$。

另外，$9901$ 是质数，可以使用快速幂求逆元。注意取模时避免负数。