AcWing 97. 约数之和

题目链接：97. 约数之和 - AcWing题库

把 $A$ 分解质因数，表示为 $p^{c_1}_1 * p^{c_2}_2 * \cdots * p^{c_n}_n$。

那么 $A^B$ 表示为 $p_1^{B * c_1} * p_2^{B * c_2} * \cdots * p_n^{B * c_n}$。

$A^B$ 的所有约数表示为集合 $\{ p^{k_1}_1 * p^{k_2}_2 * \cdots * p^{k_n}_n \}$。

其中 $0 \le k_i \le B * c_i (1 \le i \le n)$。

根据乘法分配律，$A_B$ 的所有约数之和就是：

\[(1 + p_1 + p_1^2 + \cdots + p_1^{B*c_1}) * (1 + p_2 + p_2^2 + \cdots + p_2^{B*c_2}) * \cdots * (1 + p_n + p_n^2 + \cdots + p_n^{B*c_n})\]

我们可以把该式展开，与约数集合比较。

上式中的每个括号内都是等比树列。

如果使用等比数列求和公式，需要做出发。

而答案还需要对 $9901$ 取模。

$\mod{}$ 运算只对加、减、乘有分配律，不能直接对分子、分母分别取模后再做出发。

我们可以换一种思路，使用分治法进行等比数列求和。

问题：使用分治法求 $sum(p, c) = 1 + p + p^2 + \cdots + p^c =~?$

若 $c$ 为奇数：

\[\begin{aligned} sum(p, c) & = (1 + p + \cdots + p^{ {c - 1} \over 2}) + (p^{ {c - 1} \over 2} + \cdots + p^c) \\ & = (1 + p + \cdots + p^{ {c - 1} \over 2}) + p^{ {c + 1} \over 2} * (1 + p + \cdots + p^{ {c - 1} \over 2}) \\ & = (1 + p^{ {c + 1} \over 2}) * sum(p, { {c - 1} \over 2}) \end{aligned}\]

若 $c$ 为偶数：

\[sum(p, c) = (1 + p^{c \over 2}) * sum(p, { {c \over 2} - 1}) + p^c\]

每次分治（递归）之后，问题规模均会缩小一半。
配合快速幂即可在 $\mathcal{O}(\log c)$ 的时间内求出等比数列的和。

完整代码：约数之和