快速幂 FastPow

顾名思义即快速计算幂的方法。

每个数均有二进制的表达方式，例如 十进制52647 的 二进制 为 1100 1101 1010 0111
那么则有：
2 15 + 2 14 + 2 11 + 2 10 + 2 8 + 2 7 + 2 5 + 2 2 + 2 1 + 2 0 = 52647 2^{15}+2^{14}+2^{11}+2^{10}+2^{8}+2^{7}+2^{5}+2^{2}+2^{1}+2^{0}=52647 215+214+211+210+28+27+25+22+21+20=52647

这看似与快速幂没有任何关系，但是其实这就是关键所在。

例如 计算 2^10
最简单最初想到的一定是 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 2×2×2×2×2×2×2×2×2×2 2×2×2×2×2×2×2×2×2×2 总共需要计算10次
那么如果变成 （ 2 × 2 × 2 × 2 × 2 ） × （ 2 × 2 × 2 × 2 × 2 ） （2×2×2×2×2）×（2×2×2×2×2） （2×2×2×2×2）×（2×2×2×2×2）
即 32 × 32 32×32 32×32
则总共需要计算2次

一次是计算 2 × 2 × 2 × 2 × 2 2×2×2×2×2 2×2×2×2×2
另一次是计算 32 × 32 32×32 32×32

相比之下已经极大地降低了时间复杂度。这里其实就是运用了倍增思想。

倍增法，意为成倍增长。在进行递推时，如果状态空间很大，通常的线性递推无法满足时间与空间复杂度的要求，那么我们可以通过成倍(通常以2作为基底)增长的方式，它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。

为什么通常要用2为基底各位Coders应该都知道吧

C++ 利用位运算符的模板代码

#include
using namespace std;
int fastpow(int a,int n)
{
  int ans=1;
  while(n)
  {
    if(n&1) ans=ans*a;//n的最后一位是1，表示需要乘 
    a=a*a;//递推：a->a^2->a^3->a^4 
    n>>=1;//n右移一位，把n的二进制最后一位去掉 
  }
  return ans; 
}
int main()
{
  cout << fastpow(3,2) << endl; //9
}

C语言只需稍作改动即可。
C++ 利用递归的模板代码

#include
using namespace std;
int fastpow(int m,int n) //m^n
{  
    if(n==1) return m;
    int temp=fastpow(m,n/2);
    return (n%2==0 ? 1 : m)*temp*temp;
}
int main()
{
  cout << fastpow(3,2) << endl;//9
}

C语言只需稍作改动即可。
Python利用位运算的模板代码

def fastpow(a,n):
    ans=1
    while n:
        if n&1:
            ans=ans*a
        a=a*a
        n>>=1
    return ans
​
print(fastpow(3,2))
#The Result is 9

以计算 5^21 为例 C/C++会爆
这时候最简单的方法就是用计算器 或者用Python

以计算 2^24 为例 用C/C++
位运算方法

递归方法

而用C/C++自带的pow函数则需要

可以看到在C/C++中 FastPow是比库函数快的
当然的话，如果用Python

秒杀无解
对于Python来说，
对比FastPow与库函数的Pow，
math库的pow函数

FastPow

似乎好像大概约莫着好像库函数更快些
不过对于C/C++来说，对比FastPow与库函数的Pow，
这是时间优化的一小步，却是算法竞赛的一大步[doge]
不信的话就请看例题吧類
当然快速幂不止有这一个作用，其他的作用请待后续更新~~~

如有疑问欢迎在评论区留言或者通过Email联系我

My Email:Wizzy-Ang@qq.com

我会在这里分享编程语言语法，算法，及区块链的相关知识，还有各种奇奇怪怪的小知识等着你~

虽然现在这个公众号有亿点草率 ，我会努力更新的~~~