一. 什么是快速幂：
快速幂顾名思义，就是快速算某个数的多少次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。一般一个矩阵的n次方，我们会通过连乘n-1次来得到它的n次幂。但做下简单的改进就能减少连乘的次数，方法如下：把n个矩阵进行两两分组，比如：A*A*A*A*A*A => (A*A)*(A*A)*(A*A)。这样变的好处是，你只需要计算一次A*A，然后将结果(A*A)连乘自己两次就能得到A^6，即(A*A)^3=A^6。算一下发现这次一共乘了3次，少于原来的5次。但是当n非常大的时候，其实效率也没有比直接乘号多少。
二. 二分思想求矩阵的快速幂：
首先大家要明白任何一个数都可以用二进制数来表示，比如十进制数字7可以表示为111（2），因此假设我们要求a^b，就可以把b分解成多项式，即:
b = P(n)*An+ P(n-1)*An-1+…+ P(i)*Ai+ P(i-1)*Ai-1+…+ P(0)*A0
ab= a P(n)*An + P(n-1)*An-1+…+ P(i)*Ai + P(i-1)*Ai-1 +…+ P(0)*A0= a P(n)*An * a P(n-1)*An-1 * a P(i)*Ai* …* a P(0)*A0
上面的p(i)等于0或者1，所以如果p(i)=0的话，a P(i)*Ai=a0=1. 当p(i)=1时，a P(i)*Ai=a Ai,
所以A^11就等于A^(10112)=(A^8)*(A^2)*(A^1)。这里就体现了快速的效果了：原本要进行10次乘法运算现在最多只要算4次了。（4次对应的是1011总共有4个位）。可以想象一下A的1024次幂，可以由1023次乘法运算降低到11次运算了（1024=100000000002，总共11位）。
三. 算法演示：
为了更清晰的说明快速幂算法，这里以A的11次幂为例子，配了一张图来说明，这样大家都能看得懂了哈～
将11写成1011，然后按位从右到左扫描，设置一个tmp来表示当前扫描位对应的十进制幂的大小，比如第0位对应的十进制指数是1，第3位对应的十进制指数是8，因此我们每向左前进一个扫描位，tmp就double一次，这样tmp就能表示二进制位对应的十进制幂了（tmp初始值为1）。然后我们每遇到二进制位对应数字是1时，就把结果ans和tmp相乘，并且把结果复制到ans中(ans初始值为1）。好了，现在开始运行算法：
刚开始，指针指向第0位，tmp=A，并且该位对应数字是1，所以ans=ans*tmp=A。
指针扫描到第1位，tmp也已经double一次了（tmp=A2)。该位对应数字是1，所以ans=ans*tmp=A3。
指针扫描到第2位，tmp也已经double一次（tmp=A4），该位对应数字是0，所以什么都不做，继续扫描。
指针扫描到第3位，tmp也已经double一次（tmp=A8），该位都应数字是1，所以ans=ans*tmp=A11。此时，算法结束。
四. 完整代码：
1 #include <iostream> 2 using namespace std; 3 4 //计算a^bmodn 5 int modexp(int a,int b,int n) 6 { 7 int ret=1; 8 int tmp=a; 9 while(b) 10 { 11 //基数存在 12 if(b&0x1) ret=ret*tmp%n; 13 tmp=tmp*tmp%n; 14 b>>=1; 15 } 16 return ret; 17 } 18 19 int main() 20 { 21 cout<<modexp(2,10,3)<<endl; 22 return 0; 23 }