快速幂取模

快速幂取模（Modular Exponentiation） 是快速幂算法在实际工程和算法竞赛中最常见的形态。

它专门用来高效计算类似 $(a^b) \pmod m$ 的问题，即求 $a$ 的 $b$ 次方对 $m$ 取模的结果。

为什么一定要结合“取模”？

在计算机中，如果不做处理直接算 $a^b$：

• 当 $a = 2, b = 100$ 时，$2^{100}$ 已经高达 $1.26 \times 10^{30}$，早已远超 64 位整型（long long / uint64_64）的表示上限，导致整型溢出。
• 即便 Python 这种支持高精度大数的语言不会溢出，上千位甚至上万位的超大数乘法也会严重拖慢计算速度，耗尽内存。

取模的核心运算法则：

根据模算术性质，乘积的模等于模的乘积：

$(A \times B) \pmod m = [(A \pmod m) \times (B \pmod m)] \pmod m$

这意味着：我们不需要等到整个指数算完再取模，而是在乘法执行的每一步都顺手取模。这样能把中间变量一直控制在 $[0, m-1]$ 的安全范围内，完全杜绝溢出问题！

核心过程推导（二进制拆分）

快速幂取模把指数 $b$ 看作二进制数。

以计算 $3^{13} \pmod 7$ 为例：

1. 指数 $13$ 的二进制是 $(1101)_2$，即 $13 = 8 + 4 + 0 + 1$。
2. 所以 $3^{13} = 3^8 \times 3^4 \times 3^1$。
3. 算法从最低位向最高位扫描 $b$：
   • 第 0 位（1）： 包含 $3^1$，答案累乘 $3^1$，底数翻倍成 $3^2 \pmod 7$。
   • 第 1 位（0）： 不包含 $3^2$，答案不变，底数翻倍成 $3^4 \pmod 7$。
   • 第 2 位（1）： 包含 $3^4$，答案累乘 $3^4$，底数翻倍成 $3^8 \pmod 7$。
   • 第 3 位（1）： 包含 $3^8$，答案累乘 $3^8$。

每一步的累乘和底数自乘，都立刻对 $m$ 取模。

参考代码

在实现时，有两个极易被忽视的坑点需要特别注意：

1. 防止 $a \ge m$：传入前先做 a = a % m。
2. 中间乘法溢出：两个小于 $m$ 的数相乘，最大可能达到 $(m-1)^2$。如果 $m \approx 2 \times 10^9$，乘积就会达到 $4 \times 10^{18}$，必须用 64 位整数（如 C++ 的 long long）来存储中间结果。

#include <iostream>

// 计算 (a^b) % m
long long fast_power_mod(long long a, long long b, long long m) {
    long long ans = 1;
    a %= m; // 防止 a 本身比 m 大

    while (b > 0) {
        // 如果 b 的当前二进制最低位为 1
        if (b & 1) {
            ans = (ans * a) % m; // 累乘当前权重的底数，并取模
        }
        a = (a * a) % m; // 底数自乘翻倍，并取模
        b >>= 1;         // b 右移一位，相当于 b /= 2
    }

    return ans;
}

int main() {
    // 示例：计算 (2^1000) % 1000000007
    std::cout << fast_power_mod(2, 1000, 1000000007) << std::endl;
    return 0;
}

复杂度与经典应用

典型应用场景：

1. 密码学（RSA 加密算法）： RSA 的核心解密/加密公式就是大数快速幂取模，例如 $C = M^e \pmod n$，其中指数 $e$ 和模数 $n$ 通常长达 2048 位。
2. 求乘法逆元： 基于费马小定理（$p$ 为质数时，$a^{p-1} \equiv 1 \pmod p$），取模意义下的逆元 $a^{-1} \pmod p$ 可以通过计算 $a^{p-2} \pmod p$ 直接获得。
3. 米勒-拉宾（Miller-Rabin）素数测试： 极其高效的大数概率素数检测算法，核心依赖快速幂取模。