快速幂详解

快速幂的用途

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

    }

}

上一篇:Vasya and Shifts CodeForces - 832E (高斯消元)


下一篇:2019牛客国庆集训派对day1