什么是快速幂？

在计算形如 a^b（a 的 b 次方）的表达式时，最直接的方法是进行 b-1 次乘法（a * a * ... * a）。这种方法的时间复杂度是 O(b)，当 b 非常大时，计算会非常耗时。

快速幂（Fast Exponentiation / Exponentiation by Squaring） 是一种高效计算幂的算法，它巧妙地利用了指数 b 的二进制表示和乘法的结合律，将时间复杂度显著降低到 O(log b)。

核心思想：任何一个正整数 b 都可以表示为其二进制形式。例如，13 的二进制是 1101。那么 a¹³ = a^{(8 + 4 + 0 + 1)} = a⁸ * a⁴ * a¹。我们发现，只需要计算 a¹, a², a⁴, a⁸, ... 这些底数的平方项，然后根据 b 的二进制位是否为 1，来决定是否将对应的底数平方项乘入最终结果。

快速幂的应用场景：

• 大整数幂运算，尤其是在需要取模（Modulo）的场景下，防止结果溢出。
• 组合数学中的计算（如计算组合数 C(n, k) mod p 时可能涉及逆元，而逆元常用快速幂计算）。
• 矩阵快速幂：用于加速计算矩阵的幂，常用于解决线性递推关系问题（如斐波那契数列的 O(log n) 解法）。
• 密码学中的 RSA 等算法。

动态演示：计算 a^b

快速幂的非递归 C++ 实现

下面是快速幂算法最常见的迭代（非递归）实现方式。它利用位运算 `(b & 1)` 来判断二进制最低位是否为 1，以及 `(b >>= 1)` 来将指数右移一位（相当于除以 2）。

// C++ 快速幂函数 (非递归)
#include 

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

// 计算 a^b 的结果
ll qpow(ll a, ll b) {
    ll res = 1;  // 初始化结果为 1 (任何数的 0 次方都是 1)

    // 当指数 b 大于 0 时循环
    while (b > 0) {
        // 检查 b 的当前最低二进制位是否为 1
        if (b & 1) { // 等价于 b % 2 == 1
            // 如果是 1，则将当前的底数 a 乘入结果 res
            res = res * a;
        }

        // 将底数 a 平方，为下一次迭代做准备 (计算 a^2, a^4, a^8, ...)
        a = a * a;

        // 将指数 b 右移一位 (相当于 b = b / 2)，处理下一位二进制位
        b >>= 1; // 等价于 b /= 2
    }

    // 循环结束后，res 就是 a^b 的结果
    return res;
}

int main() {
    ll base = 2;
    ll exponent = 10;
    ll result = qpow(base, exponent);
    // 输出：2^10 = 1024
    std::cout << base << "^" << exponent << " = " << result << std::endl;
    return 0;
}

注意： 这个基础版本没有处理模运算，如果 a 或 b 很大，`res` 和 `a` 可能在计算过程中超出 `long long` 的范围导致溢出。对于大数运算，通常需要结合模运算（见下一页）。

复杂度分析

• 时间复杂度：O(log b)

  循环的次数取决于指数 b 的二进制位数。一个数 b 的二进制位数大约是 log₂b。每次循环内部的操作（位运算、乘法）都是常数时间 O(1)。因此，总时间复杂度为 O(log b)。这比 O(b) 的朴素算法快得多。

• 空间复杂度：O(1)

  该算法只使用了固定数量的额外变量（`res`, `a`, `b` 的副本或自身），与输入规模 b 无关。因此，空间复杂度是 O(1)。

算法原理解析（再回顾 2¹⁰）

1. 初始化： `res = 1`, `a = 2`, `b = 10`。
2. b = 10 (二进制 1010):
   • 最低位为 0 (`10 & 1 == 0`)。不乘 `res`。 `a` 变为 `2*2 = 4`。`b` 变为 `10 >> 1 = 5`。
3. b = 5 (二进制 101):
   • 最低位为 1 (`5 & 1 == 1`)。`res` 变为 `1 * 4 = 4`。 `a` 变为 `4*4 = 16`。`b` 变为 `5 >> 1 = 2`。
4. b = 2 (二进制 10):
   • 最低位为 0 (`2 & 1 == 0`)。不乘 `res`。 `a` 变为 `16*16 = 256`。`b` 变为 `2 >> 1 = 1`。
5. b = 1 (二进制 1):
   • 最低位为 1 (`1 & 1 == 1`)。`res` 变为 `4 * 256 = 1024`。 `a` 变为 `256*256 = 65536`。`b` 变为 `1 >> 1 = 0`。
6. b = 0: 循环结束。返回 `res = 1024`。

可以看到，只有当 b 的二进制位为 1 时 (对应 2¹ 和 2³ 位，即指数中的 2 和 8)，当时的 a 值 (分别是 4=2² 和 256=2⁸) 才被乘入结果。最终结果 = 2² * 2⁸ = 2¹⁰。

为什么需要模运算？

在算法竞赛和实际应用中，直接计算 a^b 的结果往往非常巨大，会远远超过标准整型（甚至是 `long long`）的表示范围，导致溢出。然而，很多问题只关心结果对一个特定的数 `m` 取模（取余数）后的值，即计算 (a^b) mod m。

幸运的是，模运算具有良好的性质，可以与乘法结合：

(x * y) mod m = ((x mod m) * (y mod m)) mod m

这意味着我们可以在快速幂的每一步乘法之后都进行取模操作，从而保证中间结果和最终结果都不会溢出（只要 m 在整型范围内）。

模意义下的快速幂 C++ 实现

// C++ 模意义下的快速幂函数
#include 

typedef long long ll;

// 计算 (a^b) % mod 的结果
ll qpow_mod(ll a, ll b, ll mod) {
    ll res = 1;          // 初始化结果为 1
    a %= mod;            // 预处理：先将底数 a 对 mod 取模，防止 a 本身就很大

    // 如果 a 为 0，且 b 不为 0，则结果为 0
    // （注意：0^0 通常定义为 1，这里简单处理，实际应用可能需区分）
    if (a == 0 && b != 0) return 0;

    while (b > 0) {
        // 如果当前二进制位为 1
        if (b & 1) {
            // 将当前底数乘入结果，并立即取模
            res = (res * a) % mod;
        }

        // 底数平方，并立即取模
        // 注意：这里 a*a 可能溢出，如果 mod*mod 接近 LLONG_MAX
        // 对于极大的 mod，可能需要使用 __int128 或 快速乘 (下面会提到)
        a = (a * a) % mod;

        // 指数右移
        b >>= 1;
    }

    // 返回最终结果
    return res;
}

int main() {
    ll base = 3;
    ll exponent = 200;
    ll modulus = 13;
    ll result = qpow_mod(base, exponent, modulus);
    // 输出：(3^200) % 13 = 9 (可以通过费马小定理验证 3^12 = 1 mod 13, 200 = 16*12 + 8, 所以 3^200 = 3^8 mod 13)
    std::cout << "(" << base << "^" << exponent << ") % " << modulus << " = " << result << std::endl; // 输出 9
    return 0;
}

相关数论定理（可选了解）

• 模运算性质： 上面提到的 `(x * y) mod m = ((x mod m) * (y mod m)) mod m` 是基础。还有 `(x + y) mod m = ((x mod m) + (y mod m)) mod m`。
• 费马小定理 (Fermat's Little Theorem)： 如果 p 是一个质数，并且整数 a 不是 p 的倍数（即 a 和 p 互质），那么 a^p-1 ≡ 1 (mod p)。这可以用来降幂，例如计算 a^b mod p 时，可以将 b 对 p-1 取模，即 a^b ≡ a^{b mod (p-1)} (mod p)。**注意：** 这只适用于模数 p 是质数的情况。
• 欧拉定理 (Euler's Totient Theorem)： 如果 a 和 n 是互质的正整数，那么 a^φ(n) ≡ 1 (mod n)，其中 φ(n) 是欧拉函数，表示小于或等于 n 的正整数中与 n 互质的数的数目。费马小定理是欧拉定理在 n 为质数时的特例（此时 φ(p) = p-1）。欧拉定理适用于模数 n 不一定是质数的情况，但需要计算欧拉函数值。
• 扩展欧拉定理： 对于任意正整数 a 和 n，以及任意整数 b ≥ φ(n)，有 a^b ≡ a^{(b mod φ(n)) + φ(n)} (mod n)。这个定理甚至在 a 和 n 不互质时也适用（当 b ≥ φ(n) 时）。

虽然快速幂本身不直接依赖这些定理，但这些定理在处理模幂问题时（特别是降幂）非常有用，常与快速幂结合使用。

动态演示：计算 (a^b) mod m

⚠️ 常见陷阱与注意事项

• 整型溢出： 这是最常见的问题。即使最终结果在 `long long` 范围内，中间计算 `res * a` 或 `a * a` 也可能溢出。
  • **解决方案：** 始终使用 `long long` 类型存储底数 `a` 和结果 `res`。在进行模运算时，确保 `mod` 也在合理范围内。对于极大的 `mod`（例如 `mod * mod` 可能超过 `long long`），需要使用更高级的方法，如 `__int128`（GCC/Clang 支持）或**快速乘（也叫龟速乘）**来计算 `(a * b) % mod`，避免直接乘法溢出。
• 负数底数或指数：
  • **负底数 (a < 0)：** 如果指数 b 是偶数，结果为正；如果是奇数，结果为负。在模运算下，负数取模结果可能因语言而异 (C++ 结果可能是负数)。通常需要 `res = (res % mod + mod) % mod` 来确保结果为非负数。
  • **负指数 (b < 0)：** a^-b = 1 / a^b。在模运算下，这涉及到计算 a^b 的**模逆元**。如果模数 m 是质数，可以用费马小定理计算 a^m-2 mod m 作为 a 的逆元。如果 m 不是质数但与 a 互质，可以用扩展欧几里得算法或欧拉定理计算逆元。如果 a 与 m 不互质，则逆元不存在。
• 0 的处理：
  • `0^0` 通常定义为 1，但有时也视为无意义。需要根据具体题目要求处理。
  • `0^b` (b > 0) 结果为 0。
  • `a^0` (a ≠ 0) 结果为 1。
  • 在模运算 `qpow_mod(a, b, mod)` 中，如果 `a % mod == 0` 且 `b > 0`，结果应为 0。
• 模数为 1：**任何数对 1 取模的结果都是 0。`qpow_mod(a, b, 1)` 应直接返回 0 (除非 `b=0` 且 `a=0` 的特殊情况)。

⚡ 性能优化提示

• inline 函数： 如果快速幂函数在代码中被频繁调用（例如在循环内），可以考虑将其声明为 `inline`，建议编译器尝试内联展开，减少函数调用开销。但现代编译器优化已经很智能，效果不一定显著。
• 快速乘 (龟速乘)：** 当 `a * b` 可能溢出 `long long` 但 `mod` 在 `long long` 范围内时，可以用类似快速幂的思想来计算 `(a * b) % mod`。原理是将 b 看作二进制，将乘法转换为加法和倍增，每次加法后取模。时间复杂度 O(log b)。
  复制

  // 快速乘 (用于防止 a * b 溢出 long long)
  ll fast_mul(ll a, ll b, ll mod) {
      ll res = 0;
      a %= mod;
      while (b > 0) {
          if (b & 1) {
              res = (res + a) % mod;
          }
          a = (a + a) % mod; // 等价于 a = (a * 2) % mod
          b >>= 1;
      }
      return res;
  }
  
  // 在 qpow_mod 中使用快速乘
  ll qpow_mod_safe(ll a, ll b, ll mod) {
      ll res = 1;
      a %= mod;
      while (b > 0) {
          if (b & 1) {
              res = fast_mul(res, a, mod); // 使用快速乘
          }
          a = fast_mul(a, a, mod);      // 使用快速乘
          b >>= 1;
      }
      return res;
  }

• 预计算： 如果底数 a 固定，而指数 b 变化，但都在一定范围内，有时可以预计算 a 的小幂次，但这在快速幂场景下不太常见。

矩阵快速幂

其他相关应用

总结

快速幂是一种基础但极其强大的算法工具，通过简单的位运算和平方思想，将幂运算的复杂度从线性降低到对数级别。它不仅能直接解决幂运算问题，更是矩阵运算、线性递推、数论（如求逆元）等众多领域的重要组成部分。

继续探索，不断进步！