PYTHON LESSON 115
倍增与快速幂
理解“指数减半、底数平方”的倍增思想，手写快速幂求 a^b mod m，体会 O(log n) 的威力。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- while b > 0: 指数不为 0 就继续拆分
- b % 2 == 1 判断二进制当前位是否为 1
- a = a * a % m 底数每轮平方并取模
01 · 核心概念
倍增思想与 O(log n) 快速幂
倍增思想与 O(log n) 快速幂：指数从 b 变成 log2(b)：10^9 次循环变 30 次，10^18 次变 60 次。凡是“每次把规模减半”的算法都是 O(log n) 级别——二分查找如此，快速幂也如此。看到大数据先想倍增，是竞赛选手的直觉。
GESP Python 8 级 · 倍增法（快速幂）GESP Python 8 级 · 时间复杂度分析复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
02 · 语法与规则
先记住这 3 条，再开始写程序
while b > 0: 指数不为 0 就继续拆分先准确读出这条写法的结构与作用。
b % 2 == 1 判断二进制当前位是否为 1换一组最小数据，手工推演一次结果。
a = a * a % m 底数每轮平方并取模再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 快速幂：用倍增思想把十亿次乘法缩成几十次
def qpow(a, b, m):
result = 1
a = a % m
while b > 0:
if b % 2 == 1: # 二进制下这一位是 1，就要乘上当前的 a
result = result * a % m
a = a * a % m # 底数不断平方：a^1 → a^2 → a^4 → a^8 …
b = b // 2 # 指数每次减半
return result
print("2^10 mod (10^9+7) =", qpow(2, 10, 10**9 + 7))
print("3^20 mod 1000 =", qpow(3, 20, 1000))
print("7^1000000000 mod (10^9+7) =", qpow(7, 1000000000, 10**9 + 7))
print("十亿次方只循环了约 30 轮，这就是 O(log n) 的威力")2^10 mod (10^9+7) = 1024 3^20 mod 1000 = 401 7^1000000000 mod (10^9+7) = 312556845 十亿次方只循环了约 30 轮，这就是 O(log n) 的威力
指数每轮减半，循环次数约为 log2(b)：b = 10 亿时只要约 30 轮。
04 · 逐步理解
每一步只解决一个问题
- 01
先看朴素做法为什么慢
算 a^b 最直接的办法是 b 次乘法。当 b = 10^18 时，每秒算一亿次也要 300 多年。倍增法的核心观察：指数可以像切蛋糕一样对半分——a^16 = ((a^2)^2)^2)^2，4 次平方就够了。
# 朴素：result = a * a * ... * a（b 次） - 02
把指数写成二进制
任何整数都能拆成 2 的幂之和：13 = 8 + 4 + 1，所以 a^13 = a^8 × a^4 × a^1。二进制位是 1 的项乘进答案，是 0 的项跳过。这就是快速幂的全部秘密。
# 13 = 1101（二进制）→ a^13 = a^8 × a^4 × a^1 - 03
底数平方：a^1 → a^2 → a^4
循环每轮把底数平方一次：a = a * a % m。第 1 轮它代表 a^1，第 2 轮代表 a^2，第 3 轮代表 a^4……正好对应二进制从低到高的每一位。取模跟着做，数字永远不爆炸。
a = a * a % m - 04
这一位是 1 就乘进答案
b % 2 == 1 检查二进制最低位；是 1 说明当前这一位要计入答案：result = result * a % m。然后 b = b // 2 把指数右移一位，进入下一轮。
if b % 2 == 1: result = result * a % m b = b // 2 - 05
两个容易丢分的边界
① b = 0 时任何数的 0 次方是 1，循环一次都不执行，result 保持 1，天然正确。② 开头先做 a = a % m，防止底数本身比模大。Python 自带的 pow(a, b, m) 也是快速幂，考场上可以直接用。
print(pow(7, 10**9, 10**9 + 7)) # 内置同款 - 06
O(log n) 是什么概念
指数从 b 变成 log2(b)：10^9 次循环变 30 次，10^18 次变 60 次。凡是“每次把规模减半”的算法都是 O(log n) 级别——二分查找如此，快速幂也如此。看到大数据先想倍增，是竞赛选手的直觉。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行加速器，观察三个幂的结果
- 2手算 2^10 验证程序输出 1024
- 3把指数 b 改成 0，预测并核对输出
- 4数一数 b=10^9 时 while 实际循环了几轮
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
算法方法算法、复杂度与解题验证把题意转成输入、状态、规则与输出，用正确性和复杂度共同评价解法。＋
正式定义
算法是解决一类问题的有限、明确步骤。正确性说明算法对所有满足前置条件的输入都得到规定结果；时间和空间复杂度描述输入规模增长时资源使用的增长量级。
必须掌握
- 先明确输入规模 n、数据范围、目标和允许误差，再选择数据结构与算法。
- O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 表示增长量级，不是精确运行秒数。
- 顺序代码复杂度取较大项，嵌套循环常相乘，二分每步把范围缩小一半。
- 正确性可用循环不变量、数学归纳、交换论证、反证或状态定义来说明。
- 样例只验证少量输入；必须自己设计边界、极端、重复、有序/逆序和无解数据。
- 优化前先得到正确基线并测量瓶颈，不为小数据盲目增加复杂实现。
常见误区
- 只看样例通过就宣称正确
- 不看数据范围使用 O(n²)
- 二分区间开闭混用
- 把 O(n) 当成永远比 O(log n) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
Python 基础条件、循环与程序流程准确理解 if、for、while、range、break、continue 和循环嵌套，而不是背代码模板。＋
正式定义
控制流决定下一条要执行的语句。分支依据布尔条件选择路径；循环在满足规则时重复执行代码块。Python 用冒号和缩进界定代码块。
必须掌握
- if/elif/else 从上到下判断，只执行第一个为真的分支；else 不写条件。
- for 依次取得可迭代对象中的元素；range(start, stop, step) 包含 start、不包含 stop，step 不能为 0。
- while 在每轮开始前检查条件；循环体必须让状态向终止条件推进。
- break 结束最内层循环，continue 跳过本轮剩余语句，循环的 else 仅在没有被 break 终止时执行。
- 嵌套循环的总执行次数通常需要把各层次数相乘；内层 break 不会结束外层循环。
- 边界测试至少覆盖空范围、单个元素、第一项命中、最后一项命中和始终不命中。
常见误区
- range 的右端点多算或少算一次
- while 忘记更新状态造成死循环
- 把两个互斥条件写成两个独立 if
- 误以为 break 会跳出所有嵌套循环
适用边界
- 流程图是算法的表示方法，不是 Python 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
Python 基础运算符、表达式与优先级完整区分算术、比较、逻辑、成员、身份和位运算，并用优先级表消除歧义。＋
正式定义
表达式求值得到一个值。运算符规定如何组合操作数；当一个表达式含多个运算符时，优先级和结合方向决定求值顺序，括号可以明确改变顺序。
必须掌握
- / 总是得到浮点结果；// 是向负无穷方向取整的整除；% 与 // 满足 a == (a // b) * b + a % b。
- 比较可以链式书写，如 0 <= x < 10；and/or 会短路并返回最后求值的操作数，不一定返回 bool。
- == 比较值是否相等，is 比较是否为同一个对象；判断 None 应写 is None。
- in/not in 做成员测试；对 dict 测试的是键。
- 位运算作用于整数的二进制位；负整数按无限长二进制补码语义理解。
- 复杂表达式即使能靠优先级正确运行，也应使用括号表达意图。
常见误区
- 把 // 当成简单截断
- 用 is 比较数字或字符串的值
- 忘记 and 的优先级高于 or
- 连续位移、比较和逻辑运算却不加括号
适用边界
- 浮点数比较受二进制表示误差影响，需要按问题选择容差。
- 运算符可由自定义类重载，因此相同符号对不同类型可能有不同语义。
计算机基础进制、整数表示与位运算从位权理解二、八、十六进制，准确使用补码模型、移位、掩码和 Python 大整数。＋
正式定义
b 进制数按位权 b⁰、b¹…表示数值。进制只是同一个整数的书写方式；位运算直接处理整数的二进制位。Python 整数精度只受可用内存限制，负数位运算按无限长二进制补码语义定义。
必须掌握
- bin/oct/hex 生成带前缀字符串，int(text, base) 按指定进制解析；0b、0o、0x 是整数字面量前缀。
- 手工转十进制用位权展开，十进制转其他进制可连续除基取余并逆序。
- & 取共同为 1 的位，| 合并置位，^ 标记不同位，~x 等于 -x-1。
- x << k 相当于 x * 2**k；对非负整数 x >> k 相当于 x // 2**k。
- 掩码可检测、设置、清除或翻转特定位；位编号通常从最低位 0 开始。
- 固定字长语言的溢出和 Python 大整数行为不同，题目必须明确字长和有无符号。
常见误区
- 把进制字符串当成不同数值类型
- 忘记位编号从 0 开始
- 照搬固定 32 位溢出结论到 Python
- 对负数右移套用无符号模型
适用边界
- 浮点数遵循 IEEE 754 的实现细节，不使用本章的普通整数进制模型直接推导。
- 字符编码把字符映射到整数，但编码知识与整数进制书写是两个不同层次。
完成检查