C++快速幂算法实现与优化技巧

快速幂通过二进制拆分将时间复杂度从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 的二进制位。

• 初始化：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 —— 这些边界在迭代/递归里都得自然覆盖，别靠特判补救。