2010年（122）
分类： C/C++
2010-05-25 16:56:44
一、问题描述
二、解题思路
这是道数论的题，需要用到的知识点有：
（1）素因子分解唯一性定理：任意正整数都能用一种方式且只有一种方式写出素数的乘积。
如: 60 =2^2*3*5
（2）约数和公式: 将A^B 分解成素因数形式：
A^B=(p1^k1)*(p2^k2)*(p3^k3)………
那么A^B所有因子之和就是
S=(1+p1+p1^2+p1^3+…..p1^k1)*(1+p2+p2^2+p2^3+…..p2^k2)*(1+p3+…)*…………..
最后计算a^b mod MOD和求约数和的时候用到了二分的思想。
参考了：http://hi.baidu.com/aconly/blog/item/1a25845d1bfbbc44fbf2c0bf.html
