快速幂算法（模重复平方法）

题目描述：
快速幂算法用于高效计算大整数的高次幂（如 \(a^n\)），尤其适用于指数极大（如 \(n \geq 10^9\)）的场景。其核心思想是通过二分降幂，将时间复杂度从暴力算法的 \(O(n)\) 优化到 \(O(\log n)\)。若结合模运算（如计算 \(a^n \bmod m\)），则称为模重复平方法。

解题步骤（以计算 \(a^n\) 为例）：

1. 问题分析

   • 直接暴力计算需循环 \(n\) 次，当 \(n\) 极大时不可行。
   • 观察幂运算性质：\(a^n = (a^{n/2})^2\)（若 \(n\) 为偶数），或 \(a^n = a \cdot (a^{(n-1)/2})^2\)（若 \(n\) 为奇数）。通过递归或迭代可快速降幂。

2. 递归思路

   • 终止条件：若 \(n=0\)，返回 \(1\)；若 \(n=1\)，返回 \(a\)。
   • 递归拆分：
     • 若 \(n\) 为偶数：计算 \(half = a^{n/2}\)，结果为 \(half \times half\)。
     • 若 \(n\) 为奇数：计算 \(half = a^{(n-1)/2}\)，结果为 \(a \times half \times half\)。
   • 时间复杂度：\(O(\log n)\)，空间复杂度 \(O(\log n)\)（递归栈）。

3. 迭代优化（推荐）

   • 将指数 \(n\) 视为二进制数，例如 \(n = 13\)（二进制 1101）对应：

\[ a^{13} = a^{8} \cdot a^{4} \cdot a^{1} \]

• 算法步骤：
  1. 初始化结果 \(res = 1\)，底数 \(base = a\)。
  2. 遍历 \(n\) 的二进制位（从低位到高位）：
     • 若当前二进制位为 1，则 \(res = res \times base\)。
     • 每处理一位，\(base = base \times base\)（即 \(a \to a^2 \to a^4 \to \cdots\)）。
     • 右移 \(n\)（或遍历二进制位）。
  3. 返回 \(res\)。

4. 模重复平方法
   • 在每一步乘法后加入模运算，防止溢出：

\[ res = (res \times base) \bmod m, \quad base = (base \times base) \bmod m \]

• 注意：若 \(m\) 为质数，可结合费马小定理进一步优化（如 \(a^{m-1} \equiv 1 \pmod{m}\)）。

5. 示例演示（计算 \(3^{13} \bmod 10\)）：

   • \(n=13\)（二进制 1101），初始 \(res=1, base=3, m=10\)：
     • 最低位为 1：\(res = (1 \times 3) \bmod 10 = 3\)，\(base = (3 \times 3) \bmod 10 = 9\)，\(n=6\)
     • 最低位为 0：\(res\) 不变，\(base = (9 \times 9) \bmod 10 = 1\)，\(n=3\)
     • 最低位为 1：\(res = (3 \times 1) \bmod 10 = 3\)，\(base = (1 \times 1) \bmod 10 = 1\)，\(n=1\)
     • 最低位为 1：\(res = (3 \times 1) \bmod 10 = 3\)，\(base = (1 \times 1) \bmod 10 = 1\)，\(n=0\)
   • 最终结果：\(3^{13} \bmod 10 = 3\)。

6. 边界情况

   • 若 \(n=0\)，直接返回 \(1\)（除非 \(a=0\) 且 \(n=0\)，未定义）。
   • 若 \(a=0\) 且 \(n>0\)，结果为 \(0\)。
   • 注意负指数需转换为正指数处理（如 \(a^{-n} = 1/a^n\)）。

代码实现（迭代版本）：

def fast_power(a, n, m=None):
    if m is None:  # 不取模
        res, base = 1, a
        while n:
            if n & 1:  # 当前二进制位为1
                res *= base
            base *= base
            n //= 2  # 或 n >>= 1
        return res
    else:  # 模重复平方法
        res, base = 1, a % m
        while n:
            if n & 1:
                res = (res * base) % m
            base = (base * base) % m
            n //= 2
        return res