首先根据约数和定理:
对于一个大于1正整数n可以分解质因数:
n= ${p_1}^{a_1} \times {p_2}^{a_2} \times {p_3}^{a_3} \times … \times {p_k}^{a_k} $, (p1, p2, p3, …… pk) 是质数,
约数之和:
$$({p_1} ^ 0 + {p_1} ^ 1 + {p_1} ^ 2 + … + {p_1} ^ {a_1}) \times ({p_2} ^ 0 + {p_2} ^ 1 + {p_2} ^ 2 + … + {p_2} ^ {a_2}) \times … $$
$$\times ({p_k} ^ 0 + {p_k} ^ 1+{p_k} ^ 2 + … + {p_k} ^ {a_k})$$
那么这个题就可以写成下面这样
$$ ({p_1} ^ 0 + {p_1} ^ 1 + {p_1} ^ 2 + … + {p_1} ^ {a_1 \times B}) \times ({p_2} ^ 0 + {p_2} ^ 1 + {p_2} ^ 2 + … + {p_2} ^ {a_2 \times B}) \times …$$
$$ \times ({p_k} ^ 0 + {p_k} ^ 1 + {p_k} ^ 2 + … + {p_k} ^ {a_k \times B})$$
接下里的问题就是怎么求每个部分的:
$$ p^0 + p^1 + p^2 + p^3 + … + p^{a \times B}$$
$$设:k = a \times B$$
定义一个函数sum(p, k): 求$ p^0 + p^1 + p^2 + p^3 + … + p^k$的值
分三种情况讨论一下:
1: k = 0, 此时直接返回1
2: k是奇数(注意:此时一共有偶数项,因为k是从0开始的),P可以划分成下面这样
$$ (p^0 + p^1 + p^2 + .. + p^{\frac{k}{2}}) + (p^{\frac{k}{2} + 1} + p^{\frac{k}{2} + 2} + … p^{\frac{k}{2} + \frac{k}{2}}) $$
对于后面部分提取公因式 $p^{\frac{k}{2} + 1}$, 那么久变成了
$$ (p^0 + p^1 + p^2 + .. + p^{\frac{k}{2}}) + p^{\frac{k}{2} + 1} \times (p^0 + p^1 + p^2 + .. + p^{\frac{k}{2}})$$
在和并一下就是
$$ (1 + p^{\frac{k}{2} + 1}) \times (p^0 + p^1 + p^2 + .. + p^{\frac{k}{2}}) $$
对于$p^b$的可以用快速幂来求
那么此时的递推公式就是:$$(1 + p^{\frac{k}{2} + 1}) \times sum(p, k / 2)$$
3:k是偶数且k!=0,由于已经推出k是奇数和k==0的情况此时的递推公式就是
$$p^k + sum(p, k - 1)$$