快速幂通过二进制拆分将时间复杂度降至o(log n)，核心是用n&1和n>>=1处理位运算，每步乘法前必须取模防溢出，禁用std::pow，推荐迭代实现。
快速幂的核心是二进制拆分，不是循环累乘
直接写 for 循环乘 n 次，时间复杂度是 O(n)，遇到 n 上亿就卡死。快速幂真正快的地方，在于把指数按二进制位展开——比如求 a^13，13 的二进制是 1101，相当于 a^8 * a^4 * a^1，只用做 3 次乘法 + 3 次平方，总共约 O(log n) 次运算。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 别手写位运算模拟，用
n & 1判断当前位是否为 1，用n >>= 1右移，比除法更安全、更符合底层逻辑 - 底数每次自乘前，必须对模数取余（如果题目要求取模），否则
a很快溢出long long - 初始结果设为
1，不是a；指数为 0 时要能自然返回 1
带模的快速幂必须每步取余，且注意数据类型溢出
常见错误是只在最后取模：result = (result * base) % mod 写成 result = result * base % mod 看似一样，但乘法中间结果可能远超 long long 范围（比如 mod 是 1e9+7，base 是 1e9，两数相乘就到 1e18，刚好卡在 long long 上限边缘；再大一点就溢出变负数）。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 用
long long存所有中间变量，int不够用 - 乘法前加一层防溢出：如果模数较大（>1e9），考虑用
__int128（GCC 支持）或手动拆乘（不推荐除非必要） - 模数为 1 时直接返回 0（任何数 mod 1 都是 0），避免后续计算无意义
std::pow 不能替代快速幂，类型和精度都不对
std::pow(double, int) 返回 double，不仅精度丢失（整数超过 2^53 就无法精确表示），而且不支持取模，更无法处理大整数。有人试过 (long long)std::pow(a, n) % mod，结果在 a=10, n=18 就开始出错。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 彻底放弃
std::pow做整数幂运算，它不是为你设计的 - 如果只是求小指数（n ≤ 60）且不取模，用普通循环反而更清晰、无风险
- 模板化实现时，把模数作为非类型模板参数传入（如
template<long long mod></long>），编译期确定，避免运行时传参开销
递归写法简洁但容易栈溢出，迭代更稳妥
递归版本看着短：return n == 0 ? 1 : (n & 1 ? a * pow(a*a % mod, n/2) : pow(a*a % mod, n/2)) % mod，但深度是 log₂(n)，当 n 接近 2^60 时递归深度约 60 层，看似不多，但在嵌套调用多或栈空间受限环境（如 OJ 默认栈小）下可能 Segmentation fault。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 一律用迭代，代码不长，逻辑更可控
- 注意右移用
n >>= 1，不是n /= 2；前者对负数行为明确（实际中 n ≥ 0，但养成习惯） - 若需支持负指数（如求逆元），先单独判断，再用费马小定理转换，不要硬塞进同一函数
最易被忽略的是：指数为 0 时返回 1，这个边界在取模场景下仍成立（只要模数 ≠ 1）；还有就是乘法中间值哪怕只多一次没取余，整个结果就全错——它不会报错，只会静默错误。
