C++如何实现快速幂算法-C++-PHP中文网

快速幂通过二进制拆分将时间复杂度从o(b)降至o(log b)，核心是每次平方底数并根据指数二进制位决定是否累乘；需注意取模、溢出控制（如__int128）、边界处理（如b=0、mod=1）及递归栈风险。

c++如何实现快速幂算法

快速幂的核心思想是二进制拆分

直接算 a^b 的时间复杂度是 O(b)，当 b 是 10⁹ 级别时会超时；快速幂把它降成 O(log b)，关键在于把指数 b 拆成二进制位，比如 b = 13 = 1101₂，那么 a^13 = a^8 * a^4 * a^1。每次循环把底数平方（base = base * base），同时看当前 b 的最低位是否为 1（b & 1），是就乘进结果。

递归写法简洁但要注意栈溢出风险

递归版本逻辑清晰，适合理解原理，但在 b 极大（比如 1e18）或编译器未开启尾递归优化时可能爆栈：

long long pow_mod(long long a, long long b, long long mod) {
    if (b == 0) return 1 % mod;
    long long half = pow_mod(a, b >> 1, mod);
    long long res = half * half % mod;
    if (b & 1) res = res * a % mod;
    return res;
}

mod 参数必须传入，否则无法处理大数取模场景
所有中间乘法都要及时 % mod，否则 half * half 可能溢出 long long
递归深度是 log₂(b)，b=2⁶⁰ 时约 60 层，一般安全；但某些嵌入式环境或严格栈限制下仍需警惕

迭代写法更常用且可控

工业级代码基本都用迭代，避免递归开销和栈风险，也方便加边界检查：

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

long long pow_mod(long long a, long long b, long long mod) {
    long long res = 1 % mod;  // 处理 mod=1 的情况
    a %= mod;                  // 先取模，防止 a >= mod 导致后续溢出
    while (b > 0) {
        if (b & 1) res = (__int128)res * a % mod;  // 关键：用 __int128 防乘法溢出
        a = (__int128)a * a % mod;
        b >>= 1;
    }
    return res;
}

res 初始化为 1 % mod，不是 1，否则 mod=1 时结果错误
必须对 a 先做 a %= mod，否则像 a=1e18, mod=1e9+7 时，第一次 a*a 就溢出
普通 long long 乘法在 mod 接近 1e9 时极易溢出（(1e9)² = 1e18，刚好卡线），推荐用 __int128（GCC 支持）或手动拆乘法；MSVC 用户需换方案
循环中 b > 0 比 b != 0 更稳妥，避免无符号类型误判

容易被忽略的边界与类型陷阱

实际写题或工程中，这几个点错一个就会 WA 或 RE：

b 为 0 时，任何非零 a 的 0 次方是 1，但 a=0, b=0 数学上无定义——多数 OJ 要求返回 1，需按题目约定处理
如果 mod 是 int 范围，但 a 和 b 是 long long，不要漏掉 a %= mod 这步，否则 a 可能远大于 mod，导致平方后爆炸
当 mod 是 1，整个结果必为 0（除了 b=0 时是 1），但若没写 res = 1 % mod，就可能返回 1 而不是 0
不要用 int 存 b，指数常达 1e18，必须用 long long