快速幂取模

幂运算的难题

计算 $a^b \pmod n$ 似乎很简单。一个直接的想法是使用循环，将 $a$ 连乘 $b$ 次，每次相乘后都对 $n$ 取模。这可以防止中间结果溢出，正如我们在上一节学到的模乘性质一样。

然而，当指数 $b$ 变得非常大时，比如 $10^{18}$ ，这个简单的循环就会遇到大麻烦。即使计算机每秒能执行十亿次操作，完成 $10^{18}$ 次乘法也需要数万年的时间。在算法竞赛中，一秒钟通常只能承受大约一亿（ $10^8$ ）次计算。显然，我们需要一种更高效的方法。

分而治之

解决这个问题的关键在于“分治”思想，即将一个大问题分解成一个或多个结构相同但规模更小的子问题。让我们看看如何将这个思想应用于幂运算。

我们可以根据指数 $b$ 的奇偶性来分解问题：

如果 $b$ 是偶数，那么 $a^b = a^{b/2} \cdot a^{b/2} = (a^{b/2})^2$ 。计算 $a^b$ 的问题就简化成了计算 $a^{b/2}$ ，然后将结果平方。问题规模缩小了一半。
如果 $b$ 是奇数，我们可以把它写成 $a^b = a^{b-1} \cdot a$ 。由于 $b-1$ 是一个偶数，这又回到了上一种情况。所以 $a^b = (a^{(b-1)/2})^2 \cdot a$ 。

无论哪种情况，我们都成功地将计算 $a^b$ 的问题转化为了计算 $a$ 的大约 $b/2$ 次幂的问题。我们可以不断重复这个过程，直到指数降为 0，此时 $a^0 = 1$ ，这就是我们递归的终点。

a^b = \begin{cases} (a^{b/2})^2 & \text{if } b \text{ is even} \\ (a^{(b-1)/2})^2 \cdot a & \text{if } b \text{ is odd} \\ 1 & \text{if } b=0 \end{cases}

这种方法每次都将指数减半，因此被称为“二分求幂”。因为它的速度非常快，所以通常被称为“快速幂”。我们可以用递归函数轻松地实现这个逻辑。

#include <iostream>

// 使用 long long 防止中间结果溢出
typedef long long ll;

// 递归实现快速幂取模
// 计算 (base^exp) % mod
ll power_recursive(ll base, ll exp, ll mod) {
    // 递归出口：任何数的0次方都是1
    if (exp == 0) {
        return 1;
    }

    // 递归计算 (base^(exp/2)) % mod
    ll half = power_recursive(base, exp / 2, mod);
    ll result = (half * half) % mod; // 计算 (base^(exp/2))^2

    // 如果指数是奇数，需要额外乘以一个 base
    if (exp % 2 == 1) {
        result = (result * base) % mod;
    }

    return result;
}

int main() {
    ll base = 3, exp = 100, mod = 10007;
    std::cout << base << "^" << exp << " % " << mod << " = "
              << power_recursive(base, exp, mod) << std::endl;
    return 0;
}

二进制的视角

递归虽然直观，但我们也可以用一种更常见、效率稍高的迭代方法来实现快速幂。这个方法的灵感来源于指数 $b$ 的二进制表示。

以计算 $3^{13}$ 为例。数字 13 的二进制是 $1101_2$ 。我们可以将 13 分解成 2 的幂之和：

$13 = 8 + 4 + 0 + 1 = 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0$

因此， $3^{13}$ 可以写成：

$3^{13} = 3^{8+4+1} = 3^8 \cdot 3^4 \cdot 3^1$

这个转换非常关键。它告诉我们，要计算 $3^{13}$ ，我们只需要将那些对应 $b$ 的二进制位为 1 的 $a$ 的幂次（ $3^1, 3^4, 3^8$ ）相乘即可。而这些幂次（ $a^1, a^2, a^4, a^8, ...$ ）可以通过连续平方轻松得到： $a^2 = a \tcdot a$ , $a^4 = (a^2)^2$ , $a^8 = (a^4)^2$ ，以此类推。

这样，我们可以遍历 $b$ 的二进制位。如果当前位是 1，就将对应的 $a$ 的幂次累乘到最终结果中。同时，我们不断地将底数平方，以准备下一位的计算。

步骤	b 的二进制	当前位	底数 (base)	结果 (result)
初始	`1101`		`3`	`1`
1	`110`	`1`	`3 * 3 = 9`	`1 * 3 = 3`
2	`11`	`0`	`9 * 9 = 81`	`3` (不变)
3	`1`	`1`	`81 * 81`	`3 * 81`
4	`0`	`1`	`(81^2)^2`	`(3 * 81) * (81^2)`

上表（未取模）展示了这个过程。我们从 $b$ 的最低位开始检查。每一步，我们将 $b$ 右移一位（相当于除以 2），并将底数平方。如果 $b$ 的当前最低位是 1，我们就把当前的底数乘到结果中。

#include <iostream>

typedef long long ll;

// 迭代实现快速幂取模
// 计算 (base^exp) % mod
ll power_iterative(ll base, ll exp, ll mod) {
    ll result = 1;
    base %= mod; // 预处理，防止base大于mod

    while (exp > 0) {
        // 如果exp的当前最低位是1（即exp是奇数）
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }

        // 底数平方，为下一位做准备
        base = (base * base) % mod;

        // exp右移一位（相当于整除2），处理下一位
        exp /= 2;
    }
    return result;
}

int main() {
    ll base = 2, exp = 1000000000, mod = 1000000007;
    std::cout << base << "^" << exp << " % " << mod << " = "
              << power_iterative(base, exp, mod) << std::endl;
    return 0;
}

效率分析

无论是递归还是迭代的实现，快速幂算法的效率都远超暴力循环。指数 $b$ 每除以 2（或右移一位），问题规模就缩小一半。一个数 $b$ 大约可以被除以 2 多少次呢？答案是 $\log_2 b$ 次。

因此，快速幂算法的时间复杂度是 $O(\log b)$ 。这意味着即使 $b$ 高达 $10^{18}$ ，也只需要大约 $\log_2 10^{18} \approx 60$ 次乘法运算。这在任何现代计算机上都能瞬间完成，完美地解决了幂运算的效率问题。

快速幂将指数级别的计算次数，通过分治和二进制思想，成功地降到了对数级别。

现在你已经掌握了这项强大的技术，这是通向更多数论算法和组合数学计算的必经之路。

从零开始掌握模运算算法