a除以m的余数称为a对于m的模.求a^p对于m的模.其中0＜a＜2^32,0＜p＜10^100,1≤m＜2^16,其中最难处理的就是指数p了,最多能达到100位,所以实在不好处理,希望牛人能站出来指点下!

Question

a除以m的余数称为a对于m的模.求a^p对于m的模.其中0＜a＜2^32,0＜p＜10^100,1≤m＜2^16,
其中最难处理的就是指数p了,最多能达到100位,所以实在不好处理,希望牛人能站出来指点下!

Answer 1

a mod m表示a对于m的模.
那么a^p mod m = [ a^(p-1) mod m * a ] mod m
也就是可以求 a mod m = t然后求 (t * a)mod m =t ,反复
更好的用幂取模算法,若p是偶数,a^p mod m =[ a^(p/2) mod m ] ^2 mod m这可以每次把问题的规模降一倍.递归实现幂取模