倍增法：一步当两步，速度翻倍

你有没有想过，为什么计算机能快速算出 $3^{13}$ 这种很大的数？如果用乘法一个一个乘，要乘13次。但要是能“一次跳好几步”，比如先算出 $3^1$ 、再算出 $3^2$ 、再算出 $3^4$ 、再算出 $3^8$ ，然后只用其中几个乘起来（比如 $3^8 \times 3^4 \times 3^1 = 3^{13}$ ），那就只做了几次乘法。这种“每次加倍”的方法，就叫倍增法。

倍增法的核心思想是：把需要做的事情拆成若干个“2的幂次”来做，因为任何正整数都可以写成若干个2的幂次相加（也就是二进制分解）。这样，原本需要循环N次的操作，就变成了循环 $\log_2 N$ 次，速度大大提升。

生活中的跳格子——理解“二进制分解”

想象你站在一条数轴上的0点，想跳到13的位置。你每次可以跳1步、2步、4步、8步……（也就是2的幂次步）。你怎么用最少的跳跃次数到达13？

13的二进制是1101，表示 $13 = 8 + 4 + 1$ 。所以你只需要跳三次：先跳8步到8，再跳4步到12，最后跳1步到13。如果每次跳跃都只能跳固定步长（比如1步），你需要跳13次；而用2的幂次步长，只跳了3次。

倍增法就是利用这个道理：把一个大任务（比如计算大次方、找祖先、查区间最值）拆成若干个2的幂次小任务，然后“跳着”完成。

快速幂——最经典的倍增法应用

快速幂用来计算 $x^n$ （n 很大时），比如求 $3^{13} \bmod 1000000007$ 。直接乘13次要循环13次，而快速幂只需要循环4次（因为13的二进制有4位）。

核心步骤

把指数 n 写成二进制，比如 $n=13 = 1101_2$ 。
从低到高依次处理每一位：
- 如果当前位是1，就把当前底数的值乘到结果中。
- 每处理一位，底数就自乘一次（变成 $x, x^2, x^4, x^8, \dots$ ）。
- 指数右移一位（相当于去掉最低位）。

举个具体的数字例子

计算 $3^{13}$ （不取模，方便看出数值）：

初始：res = 1，x = 3，n = 13（二进制1101）
第1步：n最低位=1，res = 1×3 = 3；x = 3×3 = 9；n右移一位变为6（二进制110）
第2步：n最低位=0，不乘；x = 9×9 = 81；n右移一位变为3（二进制11）
第3步：n最低位=1，res = 3×81 = 243；x = 81×81 = 6561；n右移一位变为1（二进制1）
第4步：n最低位=1，res = 243×6561 = 1594323；x = 6561×6561；n右移一位变为0，结束

结果就是 $3^{13} = 1594323$ ，而实际 $3^{13}$ 确实等于1594323，正确。

代码实现（带中文注释）

#include <iostream>
using namespace std;

// 快速幂：计算 x^n % mod
long long quickPow(long long x, long long n, long long mod) {
    long long res = 1;          // 结果初始为1
    while (n > 0) {             // 当指数 n 不为0时循环
        if (n & 1) {            // 如果当前二进制最低位是1
            res = (res * x) % mod; // 乘上当前 x 并取模
        }
        x = (x * x) % mod;      // x 自乘变为 x^2，取模防止溢出
        n >>= 1;                // 指数右移一位（相当于除以2）
    }
    return res;
}

int main() {
    long long x = 3;            // 底数
    long long n = 13;           // 指数
    long long mod = 1000000007; // 模数（为了让结果不爆）
    cout << x << "的" << n << "次方模" << mod << " = " 
         << quickPow(x, n, mod) << endl;
    return 0;
}

运行结果：3的13次方模1000000007 = 1594323（因为3^13 = 1594323，小于模数，所以取模后不变）。

#include <iostream>
using namespace std;

// 快速幂：计算 x^n % mod
long long quickPow(long long x, long long n, long long mod) {
    long long res = 1;          // 结果初始化为1
    while (n > 0) {             // 直到指数为0
        if (n & 1) {            // 如果当前二进制位是1
            res = (res * x) % mod; // 乘上当前x
        }
        x = (x * x) % mod;      // x平方
        n >>= 1;                // n右移一位
    }
    return res;
}

int main() {
    // 测试1: 计算 2^10 % 1000
    cout << "2^10 % 1000 = " << quickPow(2, 10, 1000) << endl; // 输出24（因为1024%1000=24）

    // 测试2: 计算 5^3 % 100（普通乘法就是125%100=25）
    cout << "5^3 % 100 = " << quickPow(5, 3, 100) << endl;

    // 测试3: 大指数 3^1000000 % 1000000007
    cout << "3^1000000 % 1000000007 = " << quickPow(3, 1000000, 1000000007) << endl;

    // 测试4: 底数为0的特殊情况
    cout << "0^10 % 10 = " << quickPow(0, 10, 10) << endl; // 输出0

    // 测试5: 指数为0的情况
    cout << "7^0 % 10 = " << quickPow(7, 0, 10) << endl;   // 输出1

    return 0;
}

运行结果示例：

2^10 % 1000 = 24
5^3 % 100 = 25
3^1000000 % 1000000007 = 537390328
0^10 % 10 = 0
7^0 % 10 = 1

注意：最后的结果可能每次因为取模运算而不同，但都是正确的。

倍增法——快速跨越，一步当两步

倍增法：一步当两步，速度翻倍

生活中的跳格子——理解“二进制分解”

快速幂——最经典的倍增法应用

核心步骤

举个具体的数字例子

代码实现（带中文注释）

倍增法的其他应用（简单了解）

1. 树上最近公共祖先（LCA）

2. 区间最值查询（ST表）

3. 跳石头问题（倍增移动）

新手容易犯的错误

错误1：忘记取模导致整数溢出

错误2：指数循环条件弄错

错误3：误用 `n&1` 判断位

错误4：变量类型用错

完整可运行的示例（带多个测试）

相关指引

例题精讲