求HOJ的一个题的算法,该怎么解决
求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) .
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) .