luogu-P1226 【模板】快速幂

GESP C++ 五级练习题，考查并应用快速幂知识点。题目难度⭐⭐☆☆☆，洛谷难度等级普及−。

luogu-P1226 【模板】快速幂

题目要求

题目描述

给你三个整数 $a,b,p$ ，求 $a^b \bmod p$ 。

输入格式

输入只有一行三个整数，分别代表 $a,b,p$ 。

输出格式

输出一行一个字符串 a^b mod p=s，其中 $a,b,p$ 分别为题目给定的值， $s$ 为运算结果。

输入输出样例 #1

输入 #1

2 10 9

输出 #1

2^10 mod 9=7

说明/提示

样例解释

$2^{10} = 1024$ ， $1024 \bmod 9 = 7$ 。
数据规模与约定
对于 $100\%$ 的数据，保证 $0\le a,b < 2^{31}$ ， $a+b>0$ ， $2 \leq p \lt 2^{31}$ 。

题目分析

这道题的核心考点是 “快速幂” 算法（Fast Exponentiation），要求在 $O(\log b)$ 的近乎瞬算的时间复杂度内高效地计算出 $a^b \bmod p$ 的最终结果。

1. 为什么需要快速幂计算算法？

题目中需要求 $a^b \bmod p$ ，其中 $a,b < 2^{31}$ 。如果直接使用一个原生循环将 $a$ 连乘 $b$ 次（即最朴素的求幂算法），时间复杂度为 $O(b)$ 。在 $b$ 接近 $2^{31}$ 的情况下，哪怕是现代的高性能计算机，强行进行超过二十亿次的乘法操作也会消耗数秒甚至更久的时间，这就不可避免地会导致程序的评测出现 超时 (Time Limit Exceeded, TLE) 报错。

另外需要极度关注的是数据溢出问题：因为本题的 $a, b, p$ 范围可能达到 $2^{31}-1$ ，在实际的算术乘法过程中很容易就会发生数据越位和溢出现象（例如执行 $a \times a$ 进行底数翻倍，或者 $ans \times a$ 叠加最终结果时，相乘的结果大概率都会超出普通 $32$ 位带符号整数 int 的极限表示范围）。因此，计算的过程中必须强制使用 $64$ 位大整数类型（如示例代码中通过 typedef long long ll 简写的 ll 类型），并且在每一次乘法操作后都必须立刻对其进行模运算 % p 以防彻底溢出崩溃。

2. 快速幂的核心思想：二进制拆分

为了达到优化时间复杂度的最终目标，我们可以巧妙利用指数 $b$ 的底层“二进制”特性。任何一个十进制的正整数其实都是可以被唯一地拆解、表示为几个 $2$ 的次幂之和的。就以本道题举例，我们需要求 $a^b$ ，假设指数 $b = 11$ ：因为 $11$ 的二进制是 $(1011)_2$ ，即 $11 = 2^3 + 2^1 + 2^0 = 8 + 2 + 1$ 。所以， $a^{11} = a^{8 + 2 + 1} = a^8 \times a^2 \times a^1$ 。

在这个极其精妙的思路转变下，我们需要做的事情就不再是枯燥地去“把 $a$ 乘 $11$ 次”，而是可以先提前求出每一个在二进制位权重下的 $a$ 的次方对应值（也就是对应代码中的 base = (base * base) % mod 操作）：

末位为 1 时的处理权重: $a^1 = a$
倒数第二位权重: $a^2 = (a^1)^2$
倒数第三位权重: $a^4 = (a^2)^2$
倒数第四位权重: $a^8 = (a^4)^2$

可以看出，我们实际上只需要在 while (exp > 0) 循环中不断地对底数 $a$ 进行“自身平方乘计算”（也就是倍增基数），同时判断当前迭代中的指数 $b$ 的二进制运算“最低位”是不是为 1。这里我们直接使用了最高效的位运算 if (exp & 1)。

如果最低位为 1，说明我们需要向最后结果 ans 中乘上当前权重的底数 $a$ ；然后在处理结束之后，一定要将指数 $b$ 整体右移一位。在代码中这表现为 exp >>= 1（这在二进制本质上和 exp = exp / 2 是一模一样的），进入下一次循环判断下一权重的位。通过这一巧妙绝伦的拆解，原本需要循环运算 $b$ 次的低效乘法，被极大幅度精简和缩减到了大约 $\approx \log_2(b)$ 次。

3. 模运算的无损性质

为什么在各种连乘倍增的过程中可以随时随地放心地去取模操作呢？根据模运算的纯粹同余基本数学性质，在进行加、减、乘运算时都可以随意套用同余定理对结果和操作数进行取模：

加法取模推论：
$(A + B) \bmod p = ((A \bmod p) + (B \bmod p)) \bmod p$
减法取模推论（需要额外加 $p$ 防止结果出现负整数取模错误）：
$(A - B) \bmod p = ((A \bmod p) - (B \bmod p) + p) \bmod p$
乘法取模基础公式：
$(A \times B) \bmod p = ((A \bmod p) \times (B \bmod p)) \bmod p = (A \times (B \bmod p)) \bmod p = ((A \bmod p) \times B) \bmod p$

一句话记忆心法：“大数相乘的余数，就等于各自余数相乘后，再取一次余数。”（只要保留余数的小尾巴继续参与运算即可）

由此基础公式，我们可以推导出适用于本题代码中循环操作的两个重要推论及证明：

多项连乘步步取模推论（对应代码中的 ans = (ans * base) % mod 以及 base = (base * base) % mod）：
$(A \times B \times C) \bmod p = (((A \times B) \bmod p) \times C) \bmod p$
指数运算底数提前取模推论（对应代码 base = base % mod）：
$a^b \bmod p = ((a \bmod p)^b) \bmod p$

这两个推论与本题算法的直接关联： “快速幂”算法的本质在于化整为零，它把原本巨大的求幂运算（ $a^{11}$ ）通过二进制拆解成了多次乘法操作（ $a^8 \times a^2 \times a^1$ ）。但是拆归拆，如果等所有零碎的小块乘完合并之后再去“取模 %”，中间累积出的巨大中间结果，必定会撑爆 C++ 中常规类型 long long 的存储极限（发生所谓的“数据截断/溢出”）。
这两个推论，提供了数学支持的基础：
推论1 是“步步取余”的基石。不管我们是累乘最终答案 ans = (ans * base) % mod，还是累乘产生下一次权重的底数 base = (base * base) % mod，推论1 都从数学底层声明了“每一次趁热打铁的对中间结果取模，和放在最终合并全乘完之后取模是一致的”，从而在保证结果不出丝毫差错的情况下，将每一个计算步骤结果严丝合缝地框死在模数区间内。
推论2 是“提纯基底”的基石。在上述上千万次的连乘大工程跑起来之前，我们可以极具预见性地利用代码 base = base % mod 砍掉它天生高出 $p$ 的臃肿部分，将基数压缩。且因为数学保证了 $(a \bmod p)^b \equiv a^b \pmod p$ ，我们在起跑线上的自作主张的提前取模并不会引发蝴蝶效应。

示例代码

#include <iostream>

typedef long long ll;

// 快速幂函数，计算 (base^exp) % mod 的值。时间复杂度 O(log exp)
ll fastPow(ll base, ll exp, ll mod) {
    base = base % mod;  // 防止 base 初始就大于等于 mod 的情况，提前取模优化
    ll ans = 1;         // ans 用于记录最终的累乘结果，初始为 1
    while (exp > 0) {   // 只要指数还不为 0，就继续处理
        // 如果当前指数的最末位（二进制最低位）是 1
        // 说明当前权重下的 base 需要乘入最终结果
        if (exp & 1) {
            ans = (ans * base) % mod;
        }
        // 将底数自乘，对应二进制位左移，即 a^1 -> a^2 -> a^4 -> a^8 ...
        base = (base * base) % mod;
        // 指数右移一位，也就是除以 2，处理下一位二进制位
        exp >>= 1;
    }
    return ans;  // 返回最终计算结果
}

int main() {
    long long a, b, p;
    // 读入底数 a, 指数 b, 模数 p
    std::cin >> a >> b >> p;

    // 调用快速幂算法求解 a^b mod p
    long long result = fastPow(a, b, p);

    // 按照题目要求格式输出结果："a^b mod p=s"
    std::cout << a << "^" << b << " mod " << p << "=" << result << "\n";
    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2026年3月13日

luogu-P1303 A*B Problem luogu-P1886 【模板】单调队列 / 滑动窗口