NOIp算法(一)—— 快速幂

NOIp结束了,我退役了。
写点博客怀念一下,求大佬轻喷。

按定义来说,正常人算幂的方法是这样的

\large a^{b} = \begin{matrix}\underbrace{a\times a\times \cdots\times a}\\b\end{matrix}

复杂度 O(n)

但是我们要快
所以有神人发明出了快速幂

众所周知计算机算二进制的速度是很快的,什么东西只要带上二进制就会很快(很高大上)

例如要计算\large  a^{11},我们可以把11拆成二进制,即

\large  11=1*2^{3} + 0*2^{2}+ 1*2^{1} + 1*2^{0}

因此

\large a^{11}=a^{1*2^{3} + 0*2^{2}+ 1*2^{1} + 1*2^{0}}=a^{2^{3}}*a^{2^{1}}*a^{2^{0}}

再观察一下11的二进制1011

\large  \begin{matrix}a^{2^3}&a^{2^2}&a^{2^1}&a^{2^0}\\1&0&1&1\end{matrix}

不难发现如果二进制的第n位是1,就需要把答案乘以

\large a^{2^{n-1}}

这样把每一位都乘起来,就可以得到结果。

容易证明时间复杂度变成了  O(log n)

so,

long long qpow(long long a,long long b){\\快速幂
  long long ans = 1;//ans为要输出的答案
  long long base = a;//因为我们先要算第1位,所以先赋值base为a^(2^0),
  while(b != 0){//如果b已经移位成0,也就是每一位都处理完,就是算完了
    if(b % 2 == 1){//如果b的二进制最后一位是1的话
        ans *= base;//把答案乘以 a^(2^(n-1))
    }
    base *= base;//每一次循环自乘一次,这样保证base就为a^(2^(循环次数-1)),也就是a^(2^(n-1))
    b >>= 1;//把b右移一位,这样下次循环b的最后一位就是第二位
  }
  return ans;
}

由于伟大的位运算,判断b的二进制最后一位是否为一只需要将

\large  b\&1

所以更快的版本

long long qpow(long long a,long long b){
long long ans = 1, base = a;
while(b){
if(b & 1) ans *= base;//判断b的二进制最后一位是否为1
base *= base;
b >>= 1;
}
return ans;
}
点赞
  1. 缪雪儿.佛兰说道:
    Google Chrome 70.0.3538.110 Windows 10

    唔姆,实用

发表评论