NOIp算法（一）—— 快速幂

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

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

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

复杂度 O(n)

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

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

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

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

因此

$latex \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

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

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

$latex \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的二进制最后一位是否为一只需要将

$latex \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;
}