首页 > 代码库 > 快速幂理解

快速幂理解

 

当求解a的b次方时,如果b很大,那么时间复杂度O(n)就会很高,用快速幂可以降低复杂度。

现在假如要求a的11次方,11用二进制就可以表示成1011,那么就可以得到如下的公式:

技术分享

代码的实现很简单,如下:

typedef long long LL;  LL fun(LL x,LL n,)  {      LL res=1;      while(n>0)      {          if(n & 1)              res=(res*x);          x=(x*x);          n >>= 1;      }      return res;  }  

 

快速幂理解