快速幂算法的迭代与递归实现及模运算溢出处理

快速幂算法是用于高效计算一个数的幂次，并对结果取模的常用算法。其核心思想是将指数进行二进制分解，从而将计算时间从线性复杂度降低到对数复杂度。本文将手把手教你实现迭代与递归两种版本，并讲解如何安全地处理模运算中的溢出问题。

1. 理解快速幂的原理

计算一个数的幂，朴素方法需要进行 b-1 次乘法。例如，计算 a^b，就是 a 乘以自身 b-1 次。当 b 很大时（比如 10^18），计算次数无法接受。

快速幂算法利用了幂的二进制表示。例如，计算 a^11，指数 11 的二进制是 1011，即 11 = 8 + 2 + 1。那么 a^11 = a^(8+2+1) = a^8 a^2 a^1。

核心步骤：

1. 维护 一个变量 result，初始值为 1，用于累积最终结果。
2. 维护 一个变量 base，初始值为 a，代表当前要处理的“底数”。
3. 循环 处理指数 b 的每一位：
   • 如果当前最低位为 1，则执行 result = result * base。
   • 无论最低位是否为1，都将指数右移一位（相当于 b = b // 2），同时将 base 自乘（base = base * base）。
4. 当 b 变为 0 时，循环结束，result 即为所求。

这个公式可以概括为：$a^b \bmod m$ 的计算过程。下面用公式形式说明递归原理：将大指数问题分解为小指数问题。

$$a^b \bmod m = \begin{cases} 1 & \text{如果 } b = 0 \\ (a^{b/2} \bmod m)^2 \bmod m & \text{如果 } b \text{ 是偶数} \\ (a^{(b-1)/2} \bmod m)^2 \times a \bmod m & \text{如果 } b \text{ 是奇数} \end{cases}$$

2. 实现迭代版本

迭代版本使用循环，空间复杂度更低，是更常用的实现。

1. 定义 一个函数，接受三个参数：底数 base，指数 exponent，模数 modulus。

2. 初始化 两个变量：result = 1 用于存储结果，current_base = base % modulus 用于处理底数可能大于模数的情况。

3. 使用 while 循环，当 exponent > 0 时持续循环。

4. 在循环体内，检查 exponent 的当前最低位是否为 1（通过 exponent & 1 或 exponent % 2 == 1 判断）。

   • 如果为真，执行 result = (result * current_base) % modulus。这里立即取模是防止溢出的关键。

5. 更新 指数和底数：exponent = exponent >> 1（右移一位，等价于 exponent //= 2），current_base = (current_base * current_base) % modulus。

6. 循环结束后，返回 result。

以下是对应的 Python 代码实现：

def fast_pow_iterative(base, exponent, modulus):
    """
    快速幂迭代版本
    :param base: 底数
    :param exponent: 指数（非负整数）
    :param modulus: 模数
    :return: (base ** exponent) % modulus
    """
    result = 1
    # 先对底数取模，确保 current_base 在 [0, modulus-1] 范围内
    current_base = base % modulus

    # 当指数大于0时循环
    while exponent > 0:
        # 如果指数当前位是1，则累乘当前的底数
        if exponent & 1:  # 等价于 exponent % 2 == 1
            result = (result * current_base) % modulus  # 关键：边乘边取模，防止溢出

        # 指数右移一位（除以2），底数自乘
        exponent = exponent >> 1
        current_base = (current_base * current_base) % modulus

    return result

3. 实现递归版本

递归版本直接反映了数学公式，代码更简洁，但要注意递归深度可能受限。

1. 定义 递归函数，参数与迭代版本相同：base, exponent, modulus。

2. 设定 递归终止条件：

   • 如果 exponent == 0，返回 1。

3. 递归计算 exponent // 2 次幂的结果：half_power = fast_pow_recursive(base, exponent // 2, modulus)。

4. 根据 指数的奇偶性组合结果：

   • 如果 exponent 是偶数，返回 (half_power * half_power) % modulus。
   • 如果 exponent 是奇数，返回 (half_power * half_power % modulus * base % modulus)。注意最后要多乘一个 base。

以下是对应的 Python 代码实现：

def fast_pow_recursive(base, exponent, modulus):
    """
    快速幂递归版本
    :param base: 底数
    :param exponent: 指数（非负整数）
    :param modulus: 模数
    :return: (base ** exponent) % modulus
    """
    # 递归终止条件：指数为0
    if exponent == 0:
        return 1

    # 递归计算 exponent // 2 次幂
    half_power = fast_pow_recursive(base, exponent // 2, modulus)

    # 根据指数的奇偶性组合结果
    if exponent % 2 == 0:
        # 偶数指数：(a^(b/2))^2
        return (half_power * half_power) % modulus
    else:
        # 奇数指数：(a^(b/2))^2 * a
        return (half_power * half_power % modulus * base % modulus)

4. 处理模运算溢出

在编程中，当两个很大的数相乘时，结果可能超过语言基本数据类型（如 C/C++ 中的 int64_t）所能表示的范围，导致溢出和结果错误。模运算溢出 特指在取模过程中，中间乘积溢出的情况。

关键处理策略：在每一步乘法后立即取模。

• 原理：数学上，(a * b) % m = ((a % m) * (b % m)) % m。因此，我们可以先对乘数取模，相乘后再对结果取模。这样，参与乘法的两个数都被控制在 [0, m-1] 范围内，它们的乘积最大为 (m-1)^2。只要 m^2 不超过语言最大整数类型（如 64 位有符号整数的约 9.22e18），计算就不会溢出。

• 代码体现：在之前的代码中，result = (result * current_base) % modulus 和 current_base = (current_base * current_base) % modulus 这两行就是这一策略的体现。每次乘法操作前，乘数都已经通过取模变得很小。

• Python 的特殊性：Python 的整数类型可以自动扩展以容纳任意大的整数，因此在纯 Python 中计算大数幂模时，即使不显式取模，最终结果也不会溢出（但计算会极慢）。然而，在要求高性能或使用其他语言（如 C++、Java）时，手动进行中间取模是必须且关键的优化。

一个经过强化、适用于大数模数的 C++ 实现思路如下（使用 long long 并假设模数平方在范围内）：

long long fast_pow_with_overflow_handle(long long base, long long exponent, long long modulus) {
    long long result = 1;
    base %= modulus; // 处理底数比模数大的情况
    while (exponent > 0) {
        if (exponent & 1) {
            // 关键：使用函数处理乘法取模，防止 (result * base) 溢出
            result = mulmod(result, base, modulus);
        }
        exponent >>= 1;
        // 关键：使用函数处理乘法取模，防止 (base * base) 溢出
        base = mulmod(base, base, modulus);
    }
    return result;
}

// 一个安全的 (a * b) % m 函数实现，可以处理 m 较大的情况
long long mulmod(long long a, long long b, long long m) {
    a %= m;
    b %= m;
    // 使用俄罗斯农民乘法或内置的 __int128（如果编译器支持）来避免溢出
    long long res = 0;
    while (b > 0) {
        if (b & 1) {
            res = (res + a) % m;
        }
        a = (a * 2) % m;
        b >>= 1;
    }
    return res;
}