本文转自CSND博客：http://blog.csdn.net/u013457107/article/details/20485619
原文如下：
快速求幂算法
参见了别人的博客http://blog.sina.com.cn/s/blog_3f2fa9610100soxb.html，了解到了快速求幂的一种方法，比简单的循环相乘要大大减少乘法次数，自己学习后写的c++代码如下
1 bigint power(bigint x, int n) 2 { 3 bigint ret; 4 ret.set(1); 5 while (n!=0) 6 { 7 if (n&1==1) 8 ret=ret*x; 9 x=x*x; 10 n>>=1; 11 } 12 return ret; 13 }
这里用到了位运算，同时提高了运算效率。bigint数据类型是我自己定义的，可忽略。
接着上一步继续深入，当我们需要对一个很大的乘幂结果取模时，由于a*b%m=(a%m)*(b%m)的原理，可以将取模过程融入到快速求幂过程中，将代码稍加改进即可：
1 bigint power(bigint x, int n, int k) 2 { 3 bigint ret; 4 ret.set(1); 5 while (n!=0) 6 { 7 if (n&1==1) 8 ret=(ret*x)%k; 9 x=(x*x)%k; 10 n>>=1; 11 } 12 return ret; 13 }
同样这也是从大神的博客学来的http://blog.sina.com.cn/s/blog_8619a25801010wcy.html。看来要想学好计算机，一定要好好学数学，这是读研的重要任务之一。
原文：http://www.cnblogs.com/huashanqingzhu/p/3582572.html