Sumdiv

问题描述

求$A^B$的所有约数之和$mod\ 9901(0\leq A,B\leq 5*10^7)$

问题分析

把$A$质因数分解，表示为$p_1^{k_1}*p_2^{c_2}*\cdots*p_n^{c_n}$（其中$p_i$都是质数）

那么$A^B=(p_1^{c_1}*p_2^{c_2}*\cdots*p_n^{c_n})^B=p_1^{B*c_1}*p_2^{B*c_2}*\cdots*p_n^{B*c_n}$。

则$A^B$的所有约数为集合$\{p_1^{k_1}*p_2^{k_2}*\cdots*p_n^{k_n}\}$，其中$0\leq k_i\leq B*c_i(1\leq i\leq 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$取模，取模运算只对加、减、乘有分配率，不能直接对分子、分母分别取模后再做除法。我们可用换一种思路，使用分治法进行等比数列求和。

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

若$c$为奇数： ​ $sum(p,c)=(1+p+\cdots+p^{\frac{c-1}{2}})+(p^\frac{c+1}{2}+\cdots+p^c)$

$=(1+p+\cdots+p^{\frac{c-1}{2}})+p^\frac{c+1}2*(1+p+\cdots+p^{\frac{c-1}{2}})$

$=(1+p^\frac{c+1}2)*sum(p,\frac{c-1}2)$

若$c$为偶数，同理有：

$sum(p,c)=(1+p^\frac{c}{2})*sum(p,\frac{c}2-1)+p^c$

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

代码如下：