首先 了解一个原理 ： (a*b) mod c 等于 ( (a mod c)*(b mod c) ) mod c
我们需要求的是 ab mod c
如果b是偶数，我们可以记k = a2 mod c，那么求 kb/2 mod c 就可以了
如果b是奇数，我们也可以记k = a2 mod c，那么求 ( ( kb/2 mod c ) * a ) mod c 就可以了
那么我们可以得到以下算法：
1 int ans = 1; 2 a = a % c; 3 4 5 if(b%2==1) 6 ans = (ans * a) mod c; //如果是奇数，要多求一步，可以提前算到ans中 7 8 9 k = (a*a) % c; 10 for(int i = 1;i<=b/2;i++) {ans = (ans * k) % c;} 11 12 ans = ans % c;
我们可以看到，我们把时间复杂度变成了O(b/2)
这个过程是可以迭代下去的
对于奇数的情形会多出一项 a mod c，所以为了完成迭代，当b是奇数时，
我们通过ans = (ans * a) % c 来弥补多出来的这一项，剩余的部分就可以进行迭代了
1 int PowerMod(int a, int b, int c) 2 3 { 4 int ans = 1; 5 a = a % c; 6 7 while(b>0) 8 { 9 if(b % 2 = = 1) 10 ans = (ans * a) % c; 11 12 b = b/2; 13 a = (a * a) % c; 14 } 15 16 return ans; 17 }
时间复杂度为 O(log b)
原文：http://www.cnblogs.com/Ro0kie/p/5185724.html