快速幂的用途
顾名思义，快速幂就是很快速的幂运算，试想当你面对一个问题：求abab的时候，你的第一反应是开long long然后用for循环一点一点求。那么你就已经会了幂运算的O(b)算法。按常理来讲，这样的算法已经够用了，但是遇到一些卡时间的题目的时候还是会T，于是快速幂应运而生。简单地说，快速幂就是一种复杂度为O(logb)的求幂运算的算法。
快速幂的实现原理
对于ab，快速幂的时间复杂度是O(logb)的。一个整数可以被拆分成若干个2k的和。可以把b二进制分解，成为若干个2k的和，也就是将b转换为2进制按权相加式。
b = x020 + x121 + x222 + … + xn-12n-1。
再由ab = a^b = a^(x0*20 + x1*21 + x2*22 + … + xn-1*2n-1)，可以减少乘法操作的次数，先是基数21~2n，先进行了n次乘法，再由有效位(b的二进制形式中，数码为1的位)的位数m，额外进行m-1次的计算，则总共计算了n+m-1次，即得到计算次数不超过log2c + m – 1次。从原来的乘n次变为现在的最多乘2log2n次，因此，时间复杂度由原来的O（b）减小为现在的O（log2b）。
举个例子：
求解问题： 342。
第一步，将42二进制拆分：(42)10=(101010)2=1×25+0×24+⋯+0×20
那么， 342就变成了：342=31×32+0×16+1×8+0×4+1×2+0×1 =332*38*32
快速幂的迭代写法
int qpow(int a,int b)
{
int ret=1;
while(b>0)
{
if(b&1)
ret*=a;
a*=a;
b>>=1;
}
}
return ret;
}
通常，由于int类型以及long long类型的数值范围限制，通常遇到的OJ题目需要对运算结果取模：
快速幂取模
（a*b）%m = （（a%m）*（b%m））%m；
其实快速幂取模也是用到这个
那么根据上面的定理可以推导出另一个定理：
(ab) mod c = (a * a * a........)%c = ((a%c)*(a%c)*(a%c)*.........)%c = (a%c)b %c;
这就是快速幂取模
代码如下：
int pow_mod(int a ,int b)
{
int ans = 1 ;
int base = a % c;
while(b>0)
{
if(b&1!=0)
ans = (ans *base)%c;
}
base = (base*base)%c;
b >>= 1;
return ans;
}
快速幂的递归代码实现
在求解ab的时候
1）当b是奇数时，那么有 ab = a * ab
2）当b是偶数时，那么有 ab = a(b/2) * a(b/2)
这个东西可以用递归来实现。代码如下：
int qpow(int a,int b)
{
if(!b)
return 1;
else if(b&1)
return a*qpow(a,b-1);
else
{
int t=qpow(a,b>>1);
return t*t;
}
}