快速幂

模板 数学

7 快速幂

• 不多说，先上代码

#include <bits/stdc++.h>
using namespace std;
 
long long fastpower(long long a , long long b)
{
    long long ans = 1;
    while (b > 0)
    {
        if (b&1)
        {
            ans *= a;
        }
        a *= a;
        b >>= 1;
    }
    return ans;
}
 
int main()
{
    cout << fastpower(2,8);
}

快速幂的核心思路在下面这串代码里

while (b > 0)
{
    if (b&1)
    {
        ans *= a;
    }
    a *= a;
    b >>= 1;
}

Important

• b是我们的指数，只要大于零，我们便把这个循环继续下去

• 对任何一个数，都可以拆解为2进制的数，快速幂的核心思想在于，在幂次b二进制转化为十进制的时候$0\times 2^k$是可以不用乘进结果的而 $1\times 2^k$是需要被乘进结果的

• 示例：

• 假设我们要计算 $a^{13}$：

  • $13$ 的二进制表示是 $1101_2$。
  • 从最低位开始：
    • 第一位（1）：需要 $a^{2^0}$。
    • 第二位（0）：不需要 $a^{2^1}$。
    • 第三位（1）：需要 $a^{2^2}$。
    • 第四位（1）：需要 $a^{2^3}$。

因此，我们可以计算：

$$\begin{array}{rl}{a}^{13}& =a^{1\times 2^0}+a^{0\times 2^1}+a^{1\times 2^2}+a^{1\times 2^3}\\ & =a^{1+0+4+8}\\ & =a^{13}\end{array}$$

• 只要b大于零，我们就把他的二进制右移(除二)，这样我们就能获取下一位二进制数字
• 如果b的二进制位为1，我们就把该位置的幂次方乘进ans中，待b移位完成后ans也完成了幂运算

• 快速幂的时间复杂度为$O(\log N)$