17370845950

快速幂通过二进制拆分将时间复杂度降至O(log n)，核心是底数平方倍增、指数右移判断低位，每步取模防溢出；需特判mod==1、exp==0，负指数需费马小定理或扩展欧几里得。

快速幂的核心逻辑是二进制拆分

直接循环乘 n 次 a 的时间复杂度是 O(n)，当 n 达到 1e18 级别时必然超时。快速幂把指数看作二进制数，例如 13 = 1101₂，那么 a^13 = a^8 × a^4 × a^1 —— 只需计算 a^1, a^2, a^4, a^8... 这些“平方倍增项”，再按位累乘。

关键点在于：每次把底数自乘（base = base * base % mod），同时判断当前指数的最低位是否为 1（exp & 1），是则乘入结果。

标准快速幂模板（带模运算）

以下是最常用、最安全的递归/迭代写法。注意必须每步取模，否则中间结果极易溢出；尤其 long long 也撑不住 a=1e9, b=1e9 的平方。

long long fast_pow(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;  // 防止 base >= mod 导致后续溢出
    while (exp > 0) {
        if (exp & 1) {
            res = (res * base) % mod;
        }
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

• base %= mod 必须放在循环外首行，否则初始 base 超大时第一次 base * base 就炸
• 用 exp >>= 1 替代 exp /= 2，位运算更稳且明确意图
• 所有乘法后立刻 % mod，不能等最后再取模

处理负指数或模为 1 的边界情况

标准快速幂默认 exp ≥ 0。若题目允许负指数（如求模意义下的逆元），需额外判断：mod 必须是质数，且用费马小定理转为 fast_pow(a, mod-2, mod)；而 mod == 1 时，任何数模 1 都是 0（除 0^0 未定义），应提前返回 0。

• if (mod == 1) return 0; 必须在函数开头加，否则 base %= mod 会触发除零错误
• 负指数不属于基础快速幂范畴，强行支持需配合 std::gcd 和扩展欧几里得，不建议混进同一函数
• 如果 exp == 0，无论 base 是什么都返回 1 % mod（包括 base==0）

当 base 或 mod 超出 long long 范围时

比如 mod 是 128 位整数，或要求支持任意精度，C++ 标准库不提供原生大整数快速幂。此时有两个现实选择：

• 用 __int128（GCC 支持）临时扩宽中间乘法：将 (res * base) % mod 拆成 static_cast<__int128>(res) * base % mod
• 改用“慢速乘”替代普通乘法：把乘法本身也写成类似快速幂的加法倍增过程，避免任何一步溢出
• 引入外部库（如 Boost.Multiprecision）代价高，竞赛中基本不用

真正卡常的场景下，“慢速乘”比 __int128 更通用，但多数 OJ 的 long long + 每步取模已覆盖 99% 用例。