快速幂算法（Fast Exponentiation）

描述
快速幂算法是一种高效计算大数幂运算的方法，特别适用于模幂计算（如计算 \(a^b \mod m\)）。直接计算 \(a^b\) 的时间复杂度为 \(O(b)\)，当指数 \(b\) 非常大时（如超过 \(10^9\)），直接计算不可行。快速幂通过将指数 \(b\) 二进制分解，将时间复杂度优化至 \(O(\log b)\)。

解题过程

1. 问题分析

   • 目标：计算 \(a^b\)（或 \(a^b \mod m\)）。
   • 直接计算需要 \(b-1\) 次乘法，效率低下。
   • 核心思路：利用指数的二进制表示，将幂运算转化为多个平方运算的乘积。

2. 二进制分解思想

   • 将指数 \(b\) 表示为二进制形式，例如 \(b = 13\) 的二进制是 \(1101\)，即：

\[ b = 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 \]

• 根据幂的乘法法则，\(a^b\) 可拆解为：

\[ a^b = a^{2^3} \cdot a^{2^2} \cdot 1 \cdot a^{2^0} \]

 其中，二进制位为 0 的项可忽略（相当于乘 1）。

3. 算法步骤

   • 初始化结果 \(res = 1\)，底数 \(base = a\)。
   • 从低位到高位遍历指数 \(b\) 的二进制位（通过循环右移 \(b\)）：
     • 若当前二进制位为 1（即 \(b \mod 2 = 1\)），则将当前 \(base\) 乘到结果 \(res\) 中。
     • 更新 \(base\) 为 \(base^2\)（即计算下一个二进制位对应的幂）。
     • 将 \(b\) 右移一位（即 \(b = b // 2\)）。
   • 当 \(b\) 变为 0 时结束循环，此时 \(res\) 即为 \(a^b\)。

4. 示例演示（计算 \(3^{13}\)）

   • 初始：\(res = 1, base = 3, b = 13\)（二进制 1101）。
   • 第1轮（\(b=13\)，最低位为1）：
     • \(res = 1 \times 3 = 3\)
     • \(base = 3^2 = 9\)
     • \(b = 13 // 2 = 6\)（二进制 110）
   • 第2轮（\(b=6\)，最低位为0）：
     • \(res\) 不变（因最低位为0）
     • \(base = 9^2 = 81\)
     • \(b = 6 // 2 = 3\)（二进制 11）
   • 第3轮（\(b=3\)，最低位为1）：
     • \(res = 3 \times 81 = 243\)
     • \(base = 81^2 = 6561\)
     • \(b = 3 // 2 = 1\)（二进制 1）
   • 第4轮（\(b=1\)，最低位为1）：
     • \(res = 243 \times 6561 = 1594323\)
     • \(base = 6561^2\)（无需计算）
     • \(b = 0\)，结束。
   • 结果：\(3^{13} = 1594323\)。

5. 模幂运算扩展

   • 若需计算 \(a^b \mod m\)，只需在每次乘法和平方后立即取模：
     • \(res = (res \times base) \mod m\)
     • \(base = (base \times base) \mod m\)
   • 这避免了中间结果溢出，适用于大数计算。

6. 时间复杂度分析

   • 指数 \(b\) 的二进制位数约为 \(\log_2 b\)，故循环次数为 \(O(\log b)\)。
   • 每次循环仅需一次乘法（平方）和一次取模，整体复杂度为 \(O(\log b)\)。

关键点总结

• 快速幂通过二进制分解将线性次乘法优化为对数次。
• 结合模运算可高效处理大数模幂问题（如RSA加密）。
• 代码实现简洁，适用于递归或迭代写法。