快速幂与二进制划分 - NOI提高级教程

📖 算法原理：倍增求幂与二进制拆分定理

如果我们需要求解 $a^b \bmod m$ 的值，最朴素的方法是将 $a$ 循环累乘 $b$ 次，时间复杂度为 $O(b)$。在信息学竞赛中，当 $b$ 达到 $10^{18}$ 规模时，必须使用快速幂（Fast Exponentiation）优化。

📐 二进制拆分与倍增平方原理

任何一个正整数指数 $b$ 都可以唯一地拆分为二进制表示形式：

$b = c_k \cdot 2^k + c_{k-1} \cdot 2^{k-1} + ... + c_0 \cdot 2^0$ （其中 $c_i \in \{0, 1\}$）

根据幂底指数相乘法则，大幂次可以拆分为若干个 $a^{2^i}$ 的乘积之和：

$a^b = a^{c_k \cdot 2^k} \times a^{c_{k-1} \cdot 2^{k-1}} \times ... \times a^{c_0 \cdot 2^0}$

💡 快速幂核心步骤： - 我们从 $i=0$ 开始递增。在每一步中，底数 $a$ 不断自我平方：$a \leftarrow a^2 \bmod m$（对应大幂项 $a^{2^0}, a^{2^1}, a^{2^2}, \dots$ 递增倍增）。 - 检查指数 $b$ 的当前二进制最低位（b & 1）： - 若该位为 1（即 $c_i = 1$），则说明该倍增项被选中，我们将其乘入答案中：ans = ans * a % m； - 若该位为 0，则忽略跳过，答案不变。 - 指数右移一位：b >>= 1，继续检测下一位。由于每次指数折半，仅需 $O(\log b)$ 次平方乘法即可求解！

底数 a：指数 b：模数 m：

演示速度：

在上方输入底数、指数、模数，点击“开始快速幂”观摩二进制划分能量球合并动效！

🌪️ 二进制倍增平方划分排雷场 (Binary Splitting & Pow Flow)

📥 累计乘积答案箱 (Accumulated Answer Chamber)

ans = 1

暂无运行数据。点击开始运行。

long long qpow(long long a, long long b, long long m) {
    long long ans = 1;
    a %= m; // 基础底数取模
    while (b > 0) {
        if (b & 1) {
            ans = (ans * a) % m; // 奇数次幂，乘当前权重并模除
        }
        a = (a * a) % m; // 底数平方倍增成下一项权重
        b >>= 1; // 指数二进制右移一位
    }
    return ans;
}

📋 倍增乘除计算历史