快速幂

快速幂

问题的本质

快速幂解决的核心问题是：如何高效计算 $a^n$？

直观的做法是连续乘 $n$ 次 $a$，时间复杂度 $O(n)$。但当 $n$ 很大（比如 $n = 10^{18}$），这完全不可接受。

关键数学洞察：指数的运算天然具有二分（折半）结构。

$$a^n = \begin{cases} (a^{n/2})^2, & n \text{ 为偶数} \\ a \cdot (a^{(n-1)/2})^2 = a \cdot a^{n-1}, & n \text{ 为奇数} \end{cases}$$

每次把指数减半，问题规模指数级缩小。递归深度仅为 $\lfloor \log_2 n \rfloor$。

从数学推导到 C++ 实现

递归版 — 直接翻译数学公式

// 递归：数学定义直接映射为代码
long long qpow(long long a, long long n) {
    if (n == 0) return 1;                // 边界：a^0 = 1
    if (n & 1)                           // n 为奇数
        return a * qpow(a, n - 1);       // a^n = a · a^{n-1}
    long long half = qpow(a, n >> 1);    // 先算一半
    return half * half;                  // a^n = (a^{n/2})^2
}

递归版很好理解，但每次递归都压栈，空间 $O(\log n)$，且奇数分支实际会走两次递归。

迭代版 — 二进制视角

把指数 $n$ 写成二进制：$n = \sum b_i \cdot 2^i$，其中 $b_i \in \{0,1\}$。

那么：

$$a^n = a^{\sum b_i 2^i} = \prod_{b_i = 1} a^{2^i}$$

也就是说，只需要预先算出 $a^1, a^2, a^4, a^8, \dots$（即不断自乘），然后看 $n$ 的哪些二进制位是 1，把对应位置的值乘起来即可。

以 $n = 13 = 1101_2$ 为例：

$$a^{13} = a^{8} \cdot a^{4} \cdot a^{0} \cdot a^{1} = a^8 \cdot a^4 \cdot a^1$$

对应的二进制位从低到高：第 0 位是 1 → 乘 $a^1$，第 1 位是 0 → 跳过，第 2 位是 1 → 乘 $a^4$，第 3 位是 1 → 乘 $a^8$。

long long qpow(long long a, long long n) {
    long long res = 1;     // 单位元
    while (n) {
        if (n & 1)         // 当前最低位是 1 吗？
            res *= a;      // 是就乘上当前 a^{2^k}
        a *= a;            // 准备下一个 a^{2^{k+1}}
        n >>= 1;           // 处理下一位
    }
    return res;
}

数学直觉：这本质上是在做”指数域的加法分解”。$13 = 8+4+1$，乘法域里对应的就是 $a^8 \cdot a^4 \cdot a^1$。

带模版本 — 实际应用

const int MOD = 1e9 + 7;

long long qpow_mod(long long a, long long n) {
    long long res = 1;
    a %= MOD;
    while (n) {
        if (n & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        n >>= 1;
    }
    return res;
}