求HOJ的一个题的算法
http://acm.hit.edu.cn/hoj/problem/view?id=1991
题目大意:给一个数x,求2005^x的所有因子的和(假如设为SUM)mod 29
[解决办法]
一般的问题: 求 A^B 的所有因子之和 ( % MOD )
首先将A进行质因子分解,A=p1^c1 * p2^c2 * … * pn^cn .
那么 A^B = p1^e1 * p2^e2 * … * pn^en . ( ei = ci * B )
则 A^B的因子之和为 (1+p1+p1^2+..+p1^e1) * ( 1+p2+p2^2+….+p2^e2) * … * (1+pn+pn^2+…+pn^en) .