C++快速幂算法详解（从零开始掌握高效幂运算与取模技巧）

什么是快速幂？

快速幂（Fast Exponentiation）的核心思想是利用指数的二进制表示，将幂运算分解为若干次平方和乘法操作。例如：

要计算 313，我们可以将 13 写成二进制：13 = 11012 = 8 + 4 + 1，因此：

3¹³ = 3⁸ × 3⁴ × 3¹

而 3¹, 3², 3⁴, 3⁸ 可以通过不断平方得到：

• 3¹ = 3
• 3² = (3¹)² = 9
• 3⁴ = (3²)² = 81
• 3⁸ = (3⁴)² = 6561

这样只需 4 次平方和 3 次乘法（共约 log₂13 ≈ 4 步），远少于暴力法的 12 次乘法。

C++ 快速幂基础实现

下面是一个不带取模的快速幂函数（适用于小数据）：

long long fastPow(long long base, long long exp) {    long long result = 1;    while (exp > 0) {        if (exp & 1) {          // 如果当前二进制位是1            result *= base;        }        base *= base;           // 平方底数        exp >>= 1;              // 右移一位，相当于 exp /= 2    }    return result;}

快速幂取模（防止溢出）

在实际应用中，结果往往需要对一个大质数（如 1e9+7）取模，避免整数溢出。此时需使用 快速幂取模 技巧，这也是 算法优化技巧 中的关键一环。

根据模运算性质：
(a × b) mod m = [(a mod m) × (b mod m)] mod m

我们可以在每一步乘法后都取模：

const long long MOD = 1000000007;long long fastPowMod(long long base, long long exp, long long mod) {    long long result = 1;    base %= mod;  // 先对底数取模，防止初始值过大        while (exp > 0) {        if (exp & 1) {            result = (result * base) % mod;        }        base = (base * base) % mod;        exp >>= 1;    }    return result;}

为什么这个算法如此高效？

每次循环都将指数减半（右移一位），因此循环次数等于 exp 的二进制位数，即 O(log exp)。例如，计算 21000000000 mod 1000000007 也只需约 30 次操作！

完整示例：C++ 程序演示

#include <iostream>using namespace std;const long long MOD = 1000000007;long long fastPowMod(long long base, long long exp, long long mod) {    long long result = 1;    base %= mod;    while (exp > 0) {        if (exp & 1) {            result = (result * base) % mod;        }        base = (base * base) % mod;        exp >>= 1;    }    return result;}int main() {    long long a = 2, b = 10;    cout << a << "^" << b << " mod " << MOD << " = "          << fastPowMod(a, b, MOD) << endl;    // 输出：2^10 mod 1000000007 = 1024        // 测试大指数    a = 3; b = 1000000000LL;    cout << a << "^" << b << " mod " << MOD << " = "          << fastPowMod(a, b, MOD) << endl;        return 0;}

常见应用场景

• LeetCode / Codeforces 等平台的数学题
• RSA 加密中的模幂运算
• 组合数学中计算大数阶乘的逆元
• 矩阵快速幂（用于递推优化）

总结

通过本文，你已经掌握了 C++快速幂算法 的核心思想、代码实现和实际应用。记住关键点：

1. 将指数转为二进制，按位处理
2. 每一步平方底数，若当前位为1则乘入结果
3. 务必使用 快速幂取模 防止溢出
4. 时间复杂度仅为 O(log n)，是 C++高效幂运算 的标准解法

现在，你可以自信地在任何需要高效幂运算的场景中使用这项强大的 算法优化技巧 了！