【GESP】C++五级练习题 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
1
2 10 9
输出 #1
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$，我们在起跑线上的自作主张的提前取模并不会引发蝴蝶效应。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
