? 倍增法求幂运算：让乘法飞起来！

咱们先来个问题热身：

有一个变量 a = 2，想算 a^13（也就是 2 的 13 次方），咋算最快？

如果一步步乘：
2 × 2 × 2 × ... 得连乘 13 次，效率低得像乌龟爬树?。
有没有办法像光速战士⚡一样直接飙起来？

当然有！倍增法（又叫快速幂算法）来啦！

? 核心思想：用“二进制”分解指数

举个例子：

13 = 1101（二进制）
也就是 2^3 + 2^2 + 2^0

换句话说：

a^13 = a^(8 + 4 + 1) = a^8 × a^4 × a^1

每次都把底数平方，然后只在“1”的位上乘一下，是不是快得飞起！?

? 算法步骤

• 把指数 b 拆成二进制位

• 从低位开始看

• 如果这一位是 1，就乘当前的 a

• 每轮让 a = a * a（底数平方）

• 每轮让 b = b >> 1（指数右移）

? C++ 实现：快速幂函数

#include <iostream>
using namespace std;

typedef long long ll;

// 计算 a^b % mod
ll quick_pow(ll a, ll b, ll mod) {
    ll result = 1;     // 初始答案是1，相当于乘法的单位元
    a = a % mod;       // 先对 a 取模，防止溢出

    while (b > 0) {
        if (b & 1)      // 如果当前位是1
            result = (result * a) % mod;

        a = (a * a) % mod;  // 底数平方
        b >>= 1;            // 指数右移
    }

    return result;
}

? 小试牛刀

int main() {
    ll a = 2;
    ll b = 13;
    ll mod = 1000000007;

    cout << a << "^" << b << " mod " << mod << " = " << quick_pow(a, b, mod) << endl;

    return 0;
}

输出：

2^13 mod 1000000007 = 8192

是不是飞快地得出了结果？?

? 为什么效率高？

当 b 是 10 亿时，普通方法要乘 10 亿次，而倍增法只用乘 30 次左右。速度简直像踩了风火轮?！

? 模板拓展：递归写法也可以

ll quick_pow_recursive(ll a, ll b, ll mod) {
    if (b == 0) return 1;
    ll half = quick_pow_recursive(a, b / 2, mod);
    ll res = (half * half) % mod;
    if (b % 2 == 1)
        res = (res * a) % mod;
    return res;
}

? 小彩蛋：可以用它做什么？

• 密码学中的RSA加密

• 大数取模计算

• 快速求 a^b mod p 这样的表达式（在信息学竞赛、CSP、NOIP等场景非常常见）

? 小结（不是总结?）

? 倍增法 = 让幂运算变身光速战士
? 基于二进制思想，把乘法折叠压缩
? 从 O(b) 变成 O(log b)，效率飙升！