首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

求HOJ的一个题的算法,该怎么解决

2012-10-15 
求HOJ的一个题的算法http://acm.hit.edu.cn/hoj/problem/view?id1991题目大意:给一个数x,求2005^x的所有

求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) .

热点排行