算法手记之快速幂

yxh老师：快点做记录！！

今天我们来讲讲快速幂

快速幂是一种快速求出 a^b 的值的算法，复杂度为O(logn)，而一般的朴素算法是由一个for循环慢慢算，算完需要O(n)的时间，这显然不符合yxh老师高山流水般的思路，所以我们需要一个高效的算法来解决这个问题。

快速幂的原理

假设要求2¹¹的值，11这个数可以以二进制的形式写成11=2⁰+2¹+2³,所以2¹¹能表示为$2^{2^{0}+2^{1}+2^{3}}$220+21+23，然后拆一下就变成了：$2 ^{2^{0}}+2^{2^{1}}+2^{2^{3}}$220+221+223，原来要计算11次，现在只有3次了，是不是很神奇？
然后这里还有一个问题需要解决，对于每一个$a^{2^{k}}$a2k如何处理？很显然，既然都用到二进制了，为什么不问问神奇海螺用上位运算呢？
在这里我们要用到 & 以及 >> 这两个位运算符
&运算通常用于提取一个二进制数的末尾，就是a&1
当然，因为二进制数末尾只有1或0，所以还可以用来判断一个数的奇偶性
而>>运算就是把二进制数末尾的那个数字去掉
接下来先看代码

#define ll long long int
ll quick_exp(ll a,ll b,int mod){
   ll ans=1;
   a%=mod;
   while(b){
      if(b&1) ans=(ans*a)%mod;
      a=(a*a)%mod;
      b>>=1;
   }
   return ans;
}

其中最精髓的部分就是$a=(a*a)$a=(a∗a)这里，利用这样一个累乘器来表示二进制数每一位对应的十进制数
$a*a=a^{2^{1}}$a∗a=a21—>$a^{2}*a^{2}=a^{2^{2}}$a2∗a2=a22—>$a^{4}*a^{4}=a^{2^{3}}$a4∗a4=a23—>……
然后取一下每一位上的值（0或1）来确定要不要乘到ans上去就OK了