快速幂通过二进制拆分将时间复杂度降至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（除 
-
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% 用例。
