高次幂求模-白红宇

主要的思想是来自一个公式：a*b%c = (a%c) *(b%c) %c

基本概念及思想

对形如a^b mod m 的运算（b一般较大）

但a,b,m都在long型范围内

算法的主要思想是分治，分而治之。将大的问题分成若干个相似的较小的问题！

具体实现是用递归的方法！

举例

2^100mod 3

像这种运算如果先算出2^100 的值，然后再模上3，相信比较困难！

我们可以将100变小点

2^100=(2^50)^2 =((2^25)^2)^2=((((2^1)^2)^2)…)^2

若我们已经得出250 mod 3的值，我们便很简单地得出2^100mod 3的值。

按照上述的方法继续分下去…

最终肯定会得到2^1mod 3 这种情况！这样就好办了！这便是递归的边界，到此我们就可以返回2 mod 3的值了！

另一个问题，再分时有两种情况！

2^100=(2^50)2 , 100是偶数

2^99=(2^49)2 *2 , 99是奇数

第二种情况需要在第一种情况上乘上一次基数。

递归算法代码如下

1 long mod(long a,long b,long c) 2 { 3     long ans; 4     if(!b)return 1; 5     else if(b==1)return a%c; 6     else ans = mod(a,b/2,c); 7     ans = (ans*ans)%c; 8     if(b&1)ans = (ans*(a%c))%c; 9     return ans;10 }

另一种高效的算法是用循环代替递归算法

1 long mod_loop(long a,long b,long c) 2 { 3     long ret=1,tem=a; 4     while(b) 5     { 6         if(b&1) ret = ret*tem%c; 7         tem = tem*tem%c; 8         b>>=1; 9     }10     return ret;11 }

本文转自NewPanderKing51CTO博客，原文链接：http://www.cnblogs.com/newpanderking/archive/2012/04/24/2468656.html ，如需转载请自行联系原作者