快速幂

前言：一个乘法操作，怎么做到 $10^{18}$ 次？

在模运算那篇笔记里，我们需要频繁计算 $a^n \bmod p$ 这种东西。比如求逆元时需要算 $a^{p-2}$，而 $p$ 可以高达 $10^9+7$。

$10^9$ 次乘法，每秒做 $10^8$ 次的话，需要 10 秒——竞赛题的时间限制通常是 1 秒。更极端的情况，指数可能高达 $10^{18}$，那就要算 $10^{18}$ 次，跑完要 30 年。

所以我们需要一种完全不同的方法。

关键观察：算 $a^{16}$，不需要乘 16 次。先算 $a^2 = a \cdot a$，然后 $a^4 = a^2 \cdot a^2$，然后 $a^8 = a^4 \cdot a^4$，然后 $a^{16} = a^8 \cdot a^8$——只要 4 步。指数每次翻倍，$10^{18}$ 只需要 $\log_2(10^{18}) \approx 60$ 步。

这就是快速幂的全部动机：利用指数可以”折半”的性质，把 $n$ 次乘法压缩成 $\log n$ 次。

这篇笔记会从数学上的折半公式出发，推导出递归版、迭代版（二进制视角），最后到带模的实用版本。理解了数学原理，代码就是它的直接翻译。

快速幂

问题的本质

快速幂解决的核心问题是：如何高效计算 $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;
}

例题：求 $a^b \bmod p$

给定 $a, b, p$（$1 \le a, b, p \le 10^9$），求 $a^b \bmod p$。

直接累乘 $10^9$ 次显然超时。快速幂 $O(\log b)$ 搞定：

#include <cstdio>
using namespace std;

long long qpow(long long a, long long b, long long p) {
    long long res = 1;
    a %= p;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    long long a, b, p;
    scanf("%lld%lld%lld", &a, &b, &p);
    printf("%lld\n", qpow(a, b, p));
    return 0;
}

解析：注意 a %= p 放在循环前处理，res 和 a 每次乘完后都立即取模，保证中间值不超过 $p^2 \le 10^{18}$，在 long long 范围内。整个循环只执行 $\lfloor \log_2 b \rfloor + 1$ 次，对 $b = 10^9$ 最多 31 次迭代。