PYTHON LESSON 120
八级综合冲刺：算法优化实战
会用等差/等比数列求和公式把 O(n) 优化到 O(1)，综合运用本单元算法完成竞赛级冲刺。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- 等差求和：n * (n + 1) // 2
- 等比求和：a(q^n - 1) // (q - 1)
- pow(a, b, m) 大指数取模一步到位
01 · 核心概念
数学公式优化与竞赛综合应用
数学公式优化与竞赛综合应用：看到 n = 10^12 先心算：每秒 10^8 次操作，循环要 10^4 秒——三个多小时，必超时。竞赛铁律：数据范围决定算法。n ≤ 10^6 才能暴力，n ≤ 10^18 必须 O(1) 或 O(log n) 公式。
GESP Python 8 级 · 算法优化（数列公式）GESP Python 8 级 · 综合应用复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
02 · 语法与规则
先记住这 3 条，再开始写程序
等差求和：n * (n + 1) // 2先准确读出这条写法的结构与作用。
等比求和：a(q^n - 1) // (q - 1)换一组最小数据，手工推演一次结果。
pow(a, b, m) 大指数取模一步到位再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 算法优化实战：数学公式 vs 暴力循环
n = 10**12
# 方法一：暴力循环 O(n)——一万亿次加法，跑到天荒地老，只敢写在注释里
# total = 0
# for i in range(1, n + 1):
# total += i
# 方法二：等差数列求和公式 O(1)——一步出答案
total = n * (n + 1) // 2
print("1 + 2 + ... +", n, "=", total)
# 等比数列求和公式：1 + 2 + 4 + ... + 2^100 = 2^101 - 1
print("1+2+4+...+2^100 =", 2**101 - 1)
print("优化心得：O(n) 变 O(1)，数学公式就是最强的优化")1 + 2 + ... + 1000000000000 = 500000000000500000000000 1+2+4+...+2^100 = 2535301200456458802993406410751 优化心得：O(n) 变 O(1)，数学公式就是最强的优化
Python 整数不怕大，2^101 有 31 位也能精确输出；其他语言早溢出了。
04 · 逐步理解
每一步只解决一个问题
- 01
先估算，再动手
看到 n = 10^12 先心算：每秒 10^8 次操作，循环要 10^4 秒——三个多小时，必超时。竞赛铁律：数据范围决定算法。n ≤ 10^6 才能暴力，n ≤ 10^18 必须 O(1) 或 O(log n) 公式。
- 02
等差数列求和公式
1+2+…+n = n(n+1)÷2，首项 a、公差 d 的 n 项和为 n×a + d×n(n−1)÷2。整数运算用 // 保持精确：先乘后除，n(n+1) 必有一个是偶数，整除无误差。
total = n * (n + 1) // 2 - 03
等比数列求和公式
1+q+q²+…+q^(n−1) = (q^n − 1) ÷ (q − 1)。硬币翻倍、细胞分裂都是这个模型。q^n 太大时对模数用 pow(q, n, MOD)——快速幂在这里与数列公式胜利会师。
s = (pow(2, 101, MOD) - 1) % MOD - 04
取模世界里的除法
模意义下不能直接除：(a ÷ b) mod m ≠ (a mod m) ÷ (b mod m)。要用“逆元”：除以 b 等于乘 b^(m−2)（m 为质数时，费马小定理）。pow(b, m−2, m) 一行搞定，这是组合计数题的标准动作。
inv = pow(b, MOD - 2, MOD) - 05
八级算法全景复盘
本单元八大战法：计数原理（分类分步）、杨辉三角（递推）、快速幂（倍增）、方程与几何（数学建模）、Kruskal（贪心+并查集）、Dijkstra（堆优化）、Floyd（动态规划）、公式优化（O(1)）。看到题目先归类，再套模板。
- 06
考场 checklist
①读清数据范围选算法；②大数取模看题意；③输出格式逐字符核对（空格、换行、大小写）；④边界数据先自测：n=1、n=最大值、不可达、无解；⑤Python 记得 sys.setrecursionlimit 防深递归。冲刺成功，祝你在 GESP 八级赛场旗开得胜！
05 · 练习与检验
自己写出来，才算真正学会
- 1运行优化大师，感受 O(1) 的秒出答案
- 2手算 1+2+…+10 验证公式
- 3把 n 改成 10^18 再看速度
- 4总结本单元八大战法的适用场景
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
算法方法算法、复杂度与解题验证把题意转成输入、状态、规则与输出，用正确性和复杂度共同评价解法。＋
正式定义
算法是解决一类问题的有限、明确步骤。正确性说明算法对所有满足前置条件的输入都得到规定结果；时间和空间复杂度描述输入规模增长时资源使用的增长量级。
必须掌握
- 先明确输入规模 n、数据范围、目标和允许误差，再选择数据结构与算法。
- O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 表示增长量级，不是精确运行秒数。
- 顺序代码复杂度取较大项，嵌套循环常相乘，二分每步把范围缩小一半。
- 正确性可用循环不变量、数学归纳、交换论证、反证或状态定义来说明。
- 样例只验证少量输入；必须自己设计边界、极端、重复、有序/逆序和无解数据。
- 优化前先得到正确基线并测量瓶颈，不为小数据盲目增加复杂实现。
常见误区
- 只看样例通过就宣称正确
- 不看数据范围使用 O(n²)
- 二分区间开闭混用
- 把 O(n) 当成永远比 O(log n) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
算法方法质数、约数、最大公因数与筛法建立整数整除体系，掌握试除、欧几里得算法、唯一分解和筛法的条件与复杂度。＋
正式定义
若整数 a 能被非零整数 b 整除，则 b 是 a 的约数。大于 1 且只有 1 和自身两个正约数的整数是质数；每个大于 1 的整数都能唯一分解为质数幂的乘积（忽略次序）。
必须掌握
- 0 和 1 都不是质数；判定 n 是否为质数只需试除到 floor(sqrt(n))。
- gcd(a,b)=gcd(b,a mod b) 构成欧几里得算法；lcm(a,b)=abs(a//gcd(a,b)*b) 并要处理 0。
- 约数成对出现，可枚举到平方根；完全平方数的平方根只计一次。
- 埃氏筛从 p² 开始标记质数 p 的倍数，总体 O(n log log n)；线性筛保证每个合数被最小质因子筛一次。
- 分解质因数后，约数个数与约数和可以由各质因数指数公式计算。
- 模运算支持加减乘分配；模除法不能直接用整数除法，需满足可逆条件并求逆元。
常见误区
- 把 1 判成质数
- 试除上界漏掉平方根
- 完全平方数的约数重复统计
- 取模后直接做普通除法
适用边界
- 大整数质性测试和密码学分解需要更高级算法，不应把试除法扩展到任意规模。
- 题目若涉及负数约数、0 的约数或模数非质数，必须先明确数学定义。
数学基础计数原理、组合数与计算几何基础明确有序/无序、互斥/分步与几何退化边界，再把公式转为稳定程序。＋
正式定义
加法原理用于互斥方案分类求和，乘法原理用于依次完成步骤求积；排列关心顺序，组合不关心顺序。计算几何用坐标、向量、距离和方向关系把图形条件转成数值判定。
必须掌握
- A(n,m)=n!/(n-m)!，C(n,m)=n!/(m!(n-m)!)，并有 C(n,m)=C(n,n-m)。
- 杨辉三角递推 C(n,m)=C(n-1,m-1)+C(n-1,m)，边界 C(n,0)=C(n,n)=1。
- 取模下的组合数算法取决于 n、模数是否为质数、查询次数和是否允许预处理。
- 距离比较应优先比较平方，避免不必要的 sqrt 和浮点误差。
- 三角形必须满足任意两边之和大于第三边；共线、重合、零长度是几何边界。
- 浮点比较应按题目误差使用容差；整数坐标能用叉积时优先保持整数计算。
常见误区
- 未判断顺序是否重要就套排列组合公式
- 模意义下直接做普通除法
- 浮点数直接用 ==
- 漏掉共线或退化图形
适用边界
- 概率需要在计数结果上再建立样本空间，不等同于组合数本身。
- 复杂计算几何涉及方向、相交、凸包等更多主题，本章只覆盖课程实际使用的基础判定。
Python 基础运算符、表达式与优先级完整区分算术、比较、逻辑、成员、身份和位运算，并用优先级表消除歧义。＋
正式定义
表达式求值得到一个值。运算符规定如何组合操作数；当一个表达式含多个运算符时，优先级和结合方向决定求值顺序，括号可以明确改变顺序。
必须掌握
- / 总是得到浮点结果；// 是向负无穷方向取整的整除；% 与 // 满足 a == (a // b) * b + a % b。
- 比较可以链式书写，如 0 <= x < 10；and/or 会短路并返回最后求值的操作数，不一定返回 bool。
- == 比较值是否相等，is 比较是否为同一个对象；判断 None 应写 is None。
- in/not in 做成员测试；对 dict 测试的是键。
- 位运算作用于整数的二进制位；负整数按无限长二进制补码语义理解。
- 复杂表达式即使能靠优先级正确运行，也应使用括号表达意图。
常见误区
- 把 // 当成简单截断
- 用 is 比较数字或字符串的值
- 忘记 and 的优先级高于 or
- 连续位移、比较和逻辑运算却不加括号
适用边界
- 浮点数比较受二进制表示误差影响，需要按问题选择容差。
- 运算符可由自定义类重载，因此相同符号对不同类型可能有不同语义。
完成检查