快速幂是整数幂运算的高效算法，时间复杂度O(log n)，通过二进制拆分指数和结合律实现，支持取模防溢出，优于std::pow对大整数的精度与模运算缺陷。
什么是快速幂，为什么不用 pow 函数
标准库的 std::pow 是为浮点数设计的，对整数大幂（比如 2^1000000）既不保证精度，也不处理模运算，还可能因内部使用 double 导致溢出或舍入错误。快速幂是整数幂运算的替代方案，时间复杂度从 O(n) 降到 O(log n)，核心是利用二进制拆分指数和幂的结合律：a^b = (a^(b/2))^2 * (a if b is odd)。
手写递归版快速幂（带取模）
适合理解原理，但要注意栈深度和编译器尾递归优化不可靠。以下实现支持任意非负整数指数和可选模数：
long long quick_pow(long long base, long long exp, long long mod = 1) {
if (exp == 0) return 1 % mod;
long long half = quick_pow(base, exp >> 1, mod);
long long res = half * half % mod;
if (exp & 1) res = res * base % mod;
return res;
}
-
mod = 1表示不取模（此时% mod实际为% 1，恒为 0，需改写逻辑；更稳妥做法是把mod设为0并在函数内判断） - 乘法中间结果必须及时取模，否则
half * half可能溢出long long - 指数为 0 时返回
1 % mod，确保模 1 场景下也返回 0
迭代版快速幂（推荐用于生产环境）
避免递归开销与栈溢出风险，控制流清晰，易于嵌入循环或中断场景：
long long quick_pow_iter(long long base, long long exp, long long mod = 0) {
if (mod == 0) mod = LLONG_MAX; // 不模时设为极大值，避免取模运算
long long res = 1 % mod;
base %= mod;
while (exp > 0) {
if (exp & 1) res = (__int128)res * base % mod; // 防止乘法溢出，用 __int128（GCC/Clang）
base = (__int128)base * base % mod;
exp >>= 1;
}
return res;
}
-
__int128是 GCC/Clang 扩展，用于临时容纳long long * long long结果；若编译器不支持，需手动拆乘或用mul_mod函数模拟 - 必须先做
base %= mod，否则后续平方会失控 - 初始
res = 1 % mod处理mod == 1的边界情况
常见错误：溢出、负指数、无模大数输出
这三个问题最常导致 WA 或运行时异常：
立即学习“C++免费学习笔记（深入）”；
- 直接用
int存base和exp：指数超过2^31就截断，应统一用long long - 忽略
base本身可能为负：取模前应先base = (base % mod + mod) % mod归一化到[0, mod) - 需要输出完整大数（而非模结果）时，不能用快速幂直接算——
2^1000000有约 30 万位，得用高精度数组或std::vector模拟，快速幂结构仍可用，但乘法要重写
真正的大数幂（无模、全精度）不是“快”就能解决的，而是“存不下”，这点容易被标题里的“快速”二字误导。