快速幂

发布时间:2020年07月30日 阅读:113 次

快速幂,顾名思义,快速求幂。


a^b:朴素算法,即b个a相乘    时间复杂度O(n)


快速幂,       时间复杂度O(logn)


代码:



int Qpow(int a,int b){

    int ans=1;

    while(b!=0){

        if(b&1!=0){ans*=a;}

        a*=a;

        b>>=1;

  }

    return ans;

}

原理:把b转化为二进制,该二进制第i位的值为2^(i-1),所以a对应 b的每一位值的幂是前一位值的幂的平方。

 即      第1位的权      a^1


  第2位的权 a^2


  第3位的权 a^4


……


例:7的二进制111,a^7 =(a^(2^0)) * (a^(2^1)) * (a^(2^2))=(a^1) * (a^2) * a(a^4)


      10的二进制1010,a^10=(a^(2^1)) * (a^(2^3))=(a^2) * (a^8)


这样就可以从最低位开始处理了,


最低位为1,ans*=a;


最低位为0,不做处理。


b右移一位,a*=a;//维持a对应相应二进制位数的值。


由于计算机底层设计的原因,做加法往往比乘法快的多,因此将乘法转换为加法计算将会大大提高(大数,比较小的数也没必要)乘法运算的速度,除此之外,当我们计算a*b%mod的时候,往往较大的数计算a*b会超出long long int的范围,这个时候使用快速乘法方法也能解决上述问题. 
  快速乘法的原理就是利用乘法分配率来将a*b转化为多个式子相加的形式求解(注意这时使用乘法分配率的时候后面的一个乘数转化为二进制的形式计算).举个栗子 
  20*14 = 20*(1110)2 = 20*(2^3)*1 + 20*(2^2)*1+20*(2^1)*1+20*(2^0)*0 = 160+80+40=280. 
  这样计算了4次 而直接算的话 需要14次计算哦


矩阵快速幂

https://www.cnblogs.com/sun-of-Ice/p/9330352.html


Tag:
相关文章

发表评论: