快速幂

摘要: 本文介绍快速幂的算法原理与代码模板

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

$$a^{11} = a^{2^{0}} \times a^{2^{1}} \times a^{2^{3}}$$

在很多算法中，我们都要计算类似于 $a^{n}$ 这样的值。一个一个地乘当然是可以的，但是如果 n 很大的话，我们还可以用快速幂算法来计算。本文我们以一个模板题来介绍快速幂的算法原理、递归和二进制分解这两种实现方式及其对应的代码模板。

之后介绍一下快速幂的常见变种算法，包括模下快速幂、快速乘法、预处理 $p^{n}$，以及一些例题。

---

快速幂的算法原理

模板题

50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，$x^n$ ）。

提示：

-100.0 < x < 100.0
-231 <= n <= 231-1
-1e4 <= xn <= 1e4

示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：
输入：x = 2.10000, n = 3
输出：9.26100

示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

实现方式1: 递归

不求 $a^{n}$ 而是求 $a^{\frac{n}{2}}$, 然后先不求 $a^{\frac{n}{2}}$, 而是先求 $a^{\frac{n}{4}}$…

对以上思路最直接的实现方式是递归, 代码如下:

代码模板 (C++)

double quickpower(double x, long long n) 
{
    if (n == 0)
        return 1;
    if (n < 0)
        return 1 / quickpower(x, -n);
    double mid = quickpower(x, n / 2);
    if (n & 1)
        return mid * mid * x;
    return mid * mid;
}

实现方式2: 二进制分解

除了递归之外，还有一个代码实现技巧: 二进制分解, n -> 1, 2, 4, 8, 16, 32. n 可以分解为 2 的幂次的和. 例如 $13 = 8 + 4 + 1$, 求 $a^{13}$ 需要求 $a^{8}, a^{4}, a^{1}$。

可以用变量存 $a^{1}$, $a^{2}$, …, $a^{n - 1}$, 如果当前幂次是 n 需要的, 则加到结果中. 如何判断当前幂次是否需要, 可以用位掩码来决定, 即下面代码中的 if(n & 1)。

代码模板 (C++)

int quickpower(int a, int n)
{
    // a==0 && n==0 特判
    int ans = 1; // n = 0 时候不进循环
    while(n)
    {
        if(n & 1) 
            ans *= a;
        a *= a;
        n >>= 1;
    }
    return ans;
}

---

快速幂的一些变种

(1) 模下快速幂

当 a, n 很大时候, $a^{n}$ 显然会溢出,此时需要模下快速幂. 模下快速幂的计算方式就是一边相乘,一边取模,它的正确性需要用下面这几个数论公式来推导。

$$(a \times b)\mod c = ((a \mod c) \times (b \mod c))\mod c \\ (a + b) \mod c = ((a \mod c) + (b \mod c)) \mod c \\ (a - b) \mod c = ((a \mod c) - (b \mod c) + c) \mod c \\$$

以下代码中, 除了将参与计算的部分加了取模, 其它的部分没有改变。

代码模板 (C++)

using ll = long long;

int quickpower_mod(int a, int n, int mod) // 处理不了n是负数
{
    int ans = 1;
    while(n)
    {
        if(n & 1) 
            ans = ((ll)ans * a) % mod;
        a = (ll)a * a % mod;
        n >>= 1;
    }
    return ans % mod;
}

例题

• 372. 超级次方

题解参考 力扣372-超级次方。

(2) 预处理 $p^{n}$

有时在算法中需要频繁地求 $a^{n}$, a 不变, n 会变化, 例如字符串匹配的前缀哈希算法. 此时可以不用快速幂,而是直接将 $p^{0}$ 到 $p^{n}$ 全都预处理出来。

下面的代码用了 ull 产生溢出相当于对 $2^64$ 取模，也可以在计算过程中手动取模。

代码模板 (C++)

// pp[i] := p 的 i 次幂
vector<unsigned long long> pp(n + 1, 0); 
pp[0] = 1;
for(int i = 1; i <= n; ++i)
{
    pp[i] = pp[i - 1] * p;
}

(3) 快速乘法

有时会遇到两个 long long 相乘再模一个 long long 的问题。

例如考虑这个问题，求 $ab \mod p$，其中 $1 \leq a,b,p \leq 10^{18}$。

解法类似快速幂的思想，将 b 二进制表示，即 $b = c_{k+1}2^{k-1} + … + c_{0}2^{0}$。

若已经求出 $a \times 2^{i-1} \mod p$，则计算$a \times 2^{i} \mod p$ 时，每一步的结果都不超 $2 \times 10^{18}$。

代码模板 (C++)

ll mul(ll a, ll b, ll p)
{
    ll ans = 0;
    while(b)
    {
        if(b & 1)
            ans = (ans + a) % p;
        b >>= 1;
        a = (a * 2) % p;
    }
    return ans;
}

例题

• 29. 两数相除

题解参考 【分类讨论】力扣29-两数相除。

---