快速幂通过二进制拆分将时间复杂度从O(n)降至O(log n)，核心是底数平方、指数右移、按位累乘；需注意取模时机、边界处理（如n=0）、溢出防护及负指数/浮点数的特殊处理。
快速幂的核心思想是二进制拆分
直接算 a^n 是 O(n) 时间，而快速幂利用 n 的二进制表示，把乘法次数降到 O(log n)。比如 3^13 = 3^8 × 3^4 × 3^1，因为 13 的二进制是 1101，只对每一位为 1 的位置累乘对应幂次。
关键不是“快”，而是避免中间结果溢出和重复计算 —— 每次迭代都把底数平方、指数右移，同时按位判断是否要乘入结果。
递归写法简洁但要注意栈深和取模时机
递归版本容易理解，但 c++ 默认栈空间有限，n 超过 1e6 可能爆栈；另外，如果题目要求取模（如 1e9+7），必须在每次乘法后立刻 % MOD，否则 long long 也可能溢出。
-
if (n == 0) return 1 % MOD;—— 别漏掉 0 次方的边界 -
long long half = quick_pow(a, n >> 1);—— 用右移代替除法更安全 -
return n & 1 ? (half * half % MOD) * a % MOD : half * half % MOD;—— 先平方再乘 a，顺序不能反
迭代写法更推荐用于生产或大指数场景
迭代版空间 O(1)，无递归开销，也更容易插入调试逻辑或中断条件。核心是维护当前幂值 base 和结果 res，逐位处理 n 的二进制位。
立即学习“C++免费学习笔记（深入）”；
- 初始化：
long long res = 1, base = a % MOD;—— 底数先取模防初始溢出 - 循环条件：
while (n > 0)，别用n != 0（负数会出问题，但指数通常非负） - 判断最低位：
if (n & 1) res = res * base % MOD; - 更新：
base = base * base % MOD;，n >>= 1;
注意：所有乘法都要套 % MOD，哪怕你用了 long long —— 1e9+7 平方就超 9e18，而 long long 最大约 9.2e18。
处理负指数或浮点底数需额外封装
标准快速幂针对非负整数指数设计。若遇到负指数（如 a^(-n)），得先求 a 在模意义下的逆元（仅当 MOD 是质数且 a 不被整除时可用费马小定理），再对 |n| 快速幂；浮点数则不能直接取模，需去掉 % MOD 部分，但要注意精度丢失和 overflow 风险。
真正容易被忽略的是：很多题中 a 本身可能为 0 或 1，或 n 为 0 —— 这些边界在迭代/递归里都得自然覆盖，别靠特判补救。