快速幂的用途
顾名思义,快速幂就是很快速的幂运算,试想当你面对一个问题:求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;
}
}