快速幂通过二进制拆分将时间复杂度降至O(log b)，核心是每次平方底数、按位累乘；需用long long、每步取模、特判mod=1或b=0等边界。
快速幂的核心思想是二进制拆分
直接循环乘 n 次求 a^b 是 O(b) 时间，当 b 达到 1e9 就会超时。快速幂把指数 b 看作二进制数，比如 b = 13 = 1101₂，那么 a^13 = a^8 × a^4 × a^1 —— 只需计算 a^1, a^2, a^4, a^8... 这些“二的幂次”项，再按位累乘。
关键在于：每次把底数平方（base = base * base），同时用 b & 1 判断当前最低位是否为 1，是则乘入结果。
标准迭代写法（推荐用于竞赛）
递归写法易爆栈，且编译器不一定能优化尾递归；迭代版常数小、无函数调用开销、可轻松加模防溢出。
- 必须用
long long存结果和中间乘积，哪怕题面说答案在 int 范围内——因为a * a可能先溢出 - 模运算要每步做：
res = (res * base) % mod和base = (base * base) % mod，不能只最后取模 - 注意初始值：
res = 1，base = a % mod（防止 a 本身超模）
long long quick_pow(long long a, long long b, long long mod) {
long long res = 1;
long long base = a % mod;
while (b > 0) {
if (b & 1) res = (res * base) % mod;
base = (base * base) % mod;
b >>= 1;
}
return res;
}位运算细节：为什么用 b & 1 而不是 b % 2？
两者逻辑等价，但 b & 1 是纯位操作，无除法指令，在 x86/x64 上通常编译为单条 test 或 and 指令；而 b % 2 可能触发除法微码（尤其对非常规字长或负数）。竞赛中毫秒级差异可能决定过题与否。
立即学习“C++免费学习笔记（深入）”；
另外 b >>= 1 比 b /= 2 更安全：
- 对非负整数，二者行为一致
- 但若误传负数（如输入错误），
>>=是算术右移（符号位扩展），/=是向零取整，结果不一致；竞赛题保证b ≥ 0，所以>>=更符合快速幂语义
常见陷阱：模数为 1 或底数为 0 的边界
这些情况不会报错，但容易被忽略导致 WA：
- 如果
mod == 1，任何数的幂模 1 都是 0（除了0^0，但题目通常不定义或规定为 1）；直接返回0可省去整个循环 - 如果
a == 0 && b > 0，结果恒为 0；但a == 0 && b == 0是未定义行为，多数 OJ 规定输出 1（如 Codeforces），需看题面 - 如果
b == 0，无论a是多少（含 0），数学上a^0 = 1（0^0除外），所以循环前应特判b == 0并返回1 % mod
真正难调试的，往往是模数大、中间乘法溢出但没开 long long，或者忘了对 base 初始化取模——比如 a = 1e9+7, mod = 1e9+7，不取模会导致第一次 base * base 直接溢出。
