C++ 算法考级专栏
🎨 视觉封面【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:欧几里得辗转相除法原理、时间复杂度证明与防溢出 LCM 写法
在面对“求两个大整数 a, b(最高可达 )的最大公约数与最小公倍数”时,如果还停留在从 min(a, b) 一路递减枚举的暴力试除法,单次查询 的耗时足以让程序瞬间 TLE(运行超时);而哪怕背下了短短一行的欧几里得辗转相除法,不少同学依然会在考场上连环踩雷:初赛选择题问“100 以内哪组正整数会让辗转相除执行取模次数最多”,想当然地选了 (100, 99) 结果痛失高分;复赛求最小公倍数时顺手写下 a * b / gcd(a, b),明明最终答案连 100 万都不到,中间的 a * b 却提前撑爆整数上限溢出回绕;更有甚者在 C++11 评测环境下盲目调用 std::gcd 直接喜提 CE(编译错误)!在 GESP 五级认证以及 CSP-J/S 初赛与复赛中,欧几里得恒等式 的数论本质、“两步必减半”的 复杂度证明与相邻斐波那契数最坏退化模型、最小公倍数“先除后乘”防溢出铁律,以及裴蜀定理(Bézout's Identity)的可凑性判据,构成了初等数论模块的绝对基石。本文将从几何直觉与严谨代数两条脉络出发,把这套传承两千三百年的经典算法彻底讲透。
🎯 考纲锚点与核心痛点
📍 对应考点:掌握最大公约数(GCD)与最小公倍数(LCM)的数论定义及素因数分解关系,深入理解欧几里得辗转相除法的正确性原理与 时间复杂度,熟练编写无溢出的 GCD/LCM 代码并了解裴蜀定理的基本结论。 🎯 适用等级:
GESP 五级考点 | CSP-J/S 初赛/复赛必考
在历年 GESP 五级真题与 CSP-J 初复赛中,考生最容易在以下三大痛点上栽跟头:
- “只会死背代码,不懂为什么取模后最大公约数丝毫不变”:遇到初赛变式阅读程序题(如交换参数顺序、统计取模次数、分析最坏输入),一旦脱离模板立刻陷入迷茫,误以为最大的相邻数对
(100, 99)计算最慢; - “求最小公倍数直接写
a * b / gcd(a, b),惨遭中间乘积爆类型”:忽略了计算机算术从左往右求值的顺序——哪怕最终的lcm(a, b)完全装得下,先算a * b也会把数值凭空放大gcd(a, b)倍,瞬间击穿 32 位甚至 64 位整数边界; - “依赖非标准库函数或写错递归出口,埋下 CE 与除零 RE 隐患”:考场混用 C++17 才引入的
std::gcd与 GCC 编译器私货__gcd,或把递归基准条件错写成if (a % b == 0),一旦题中出现0直接触发除以零运行崩溃(Floating Point Exception)。
🧠 一、 核心原理深度拆解(有理论)
1. 为什么 ?几何铺砖与整除双夹证明
设 a, b 为正整数,带余除法将 a 表示为 (其中商 ,余数 ,满足 )。为什么一对大数 (a, b) 的最大公约数,会与缩小后的 (b, r) 完全相等?
我们可以用最直观的长方形正方形铺砖模型一眼看穿它的几何本质:求 gcd(a, b),等价于寻找能严丝合缝铺满长 a、宽 b 矩形而无需裁剪的最大正方形地砖边长 d。
================================================================================
【欧几里得辗转相除法的“正方形铺砖”几何直观图(以 a = 48, b = 18 为例)】
|<-------------------- a = 48 -------------------->|
+----------------+----------------+----------+-----+ ───
| | | 12×12 | 6×6 | ▲
| 18 × 18 | 18 × 18 | +-----+ │ b = 18
| 大正方形 | 大正方形 | | 6×6 | ▼
+----------------+----------------+----------+-----+ ───
|<--- b = 18 --->|<--- b = 18 --->|<--- r = 12 --->|
▶ 第 1 轮裁切:48 = 2 × 18 + 12。任何能铺满 18×18 的地砖,必然也能铺满左边的
两个 18×18 区域;因此问题瞬间等价于铺满右侧剩余的【18 × 12】矩形!
▶ 第 2 轮裁切:18 = 1 × 12 + 6,问题继续缩小为铺满右下角【12 × 6】矩形!
▶ 第 3 轮裁切:12 = 2 × 6 + 0,恰好被两个【6 × 6】正方形铺满无剩余!
故最大正方形边长 gcd(48, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6!
================================================================================从代数整除角度,只需两行即可完成双向充要证明(证 (a, b) 与 (b, r) 的全体公因数集合完全相同):
- 正向推导:设任意整数
d同时整除a和b(即 且 )。由于 ,整除具有线性组合保持性,故d必然也能整除r(即 且 ); - 反向推导:反之,若 且 ,则
d必然也能整除 (即 且 )。
既然数对 (a, b) 与数对 (b, a % b) 拥有一模一样的公因数集合,它们的最大公约数自然绝对相等!当辗转相除一路推进到余数为 0,变成 gcd(d, 0) 时(注意任何非零整数都能整除 0,因为 0 = 0 * d),最大公约数就是此时的非零数 d。
2. 为什么快如闪电?“两步必减半”定理与斐波那契最坏情况
许多初学者好奇:取模运算 r = a % b 会不会每次只减小一点点(比如从 100 变成 99、98……),从而退化成 ?答案是:绝对不可能!
(1)严格 证明:每 2 步至少折半
考察连续两步状态转移 (a, b) -> (b, r) -> (r, b % r)(不妨设 ,则 ):
- 情况 A():由于余数严格小于除数,必有 ;
- 情况 B():此时
a里最多只装得下 1 个b(即商k = 1),因此余数就是两者之差 !
无论是情况 A 还是情况 B,都有 恒成立!这意味着在辗转相除序列中,每经过 2 次取模运算,参数规模至少缩小为原来的二分之一。即便面对高达 (约 )的 long long 极限大数,总取模步数也绝不会超过 2 * 60 = 120 次,时间复杂度严格为 !
(2)初赛王牌考点:什么时候步数最多?(拉梅定理与斐波那契数列)
怎样让数字缩小得最慢,把辗转相除“卡”到最大步数?显然要让每一步的商 k 都尽可能小——即每一步商都恰好等于 1!
从终点 (1, 0) 令商全为 1 逆向倒推(),得到的序列依次是:
(1, 0) <- (1, 1) <- (2, 1) <- (3, 2) <- (5, 3) <- (8, 5) <- (13, 8) <- (21, 13) <- (34, 21) <- (55, 34) <- (89, 55) ...这正是大名鼎鼎的相邻斐波那契数(Fibonacci Numbers)!法国数学家拉梅(Gabriel Lamé)证明了:在 a >= b > 0 前提下,若欧几里得算法需要执行 k 次取模,则最小的输入正整数对恰为相邻斐波那契数 。相反,看似吓人的相邻大数 (100, 99) 第 1 步 100 % 99 = 1,第 2 步 99 % 1 = 0,仅仅 2 步就瞬间秒杀!
3. 最小公倍数(LCM)防溢出铁律与裴蜀定理导引
(1)GCD 与 LCM 的对偶恒等式及“先除后乘”铁律
从唯一分解定理来看,设 ,,则: 由于对任意两个实数恒有 ,两式相乘立即导出黄金恒等式:
但在写 C++ 代码求解 lcm(a, b) 时,下面两种写法有着满分与零分的天壤之别:
| 写法对比 | 代码表达式 | 算术求值轨迹(设 32 位无符号整数 a=80000, b=90000) |
最终结果与安全性 |
|---|---|---|---|
| 高危错误写法 | a * b / gcd(a, b) |
先算 80000 * 90000 = 7.2e9(超 溢出回绕为 2905032704),再除以 10000 |
290503(严重溢出 ❌) |
| 满分标准写法 | a / gcd(a, b) * b |
因为 gcd(a, b) 必然整除 a,先精确整除得 8,再乘 90000(推荐左乘 1LL *) |
720000(零冗余膨胀 ✅) |
(2)裴蜀定理(Bézout's Identity)核心结论
既然辗转相除每一步的余数都是前两项的整数线性组合,一路回代到开头就能证明数论名定理——裴蜀定理:
对于任意不全为
0的整数a, b,关于未知整数x, y的二元一次不定方程 有整数解的充要条件是 (即c必须是gcd(a, b)的整数倍)。特别地,ax + by所能凑出的最小正整数恰好等于 ;当且仅当a, b互质()时,存在整数x, y使得 。
例如:给你一个容量 6 升和一个容量 9 升的无刻度水壶(水无限供应),能否倒出恰好 4 升水?因为每次装满、倒空、互倒都只是在做 6x + 9y 的整数加减组合,而 gcd(6, 9) = 3,3 不能整除 4,由裴蜀定理一秒判定:永远不可能凑出 4 升!
💡 考场黄金法则(背诵直接套用):
- 【三行手写欧几里得,出口认准
b == 0】:严格 C++11 考场环境下绝不依赖std::gcd或__gcd,统一手写long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }——不仅天然兼容b == 0边界,而且当a < b时第 1 步a % b = a会自动完成两数交换,无需画蛇添足写swap!- 【求 LCM 必先除后乘,防爆套上
1LL】:凡是计算最小公倍数,肌肉记忆锁定1LL * (a / gcd(a, b)) * b——先用gcd把a缩小再乘b,彻底消灭中间乘积的无谓溢出!
🔍 二、 具象代码与数据推演(有举例)
示例:a < b 自动交换机制推演与 LCM 溢出对比实验
下面这段 24 行的标准 C++11 程序,先追踪当传入第一个参数小于第二个参数(a = 18, b = 48)时辗转相除每一轮的变量演变,随后演示 a = 80000, b = 90000 在 32 位无符号整数下“先乘后除”与“先除后乘”的真实输出差异:
#include <iostream>
using namespace std;
int trace_gcd(int a, int b) {
int step = 0;
while (b != 0) {
int r = a % b;
step++;
cout << "Step " << step << ": a=" << a << ", b=" << b << " -> r=" << r << endl;
a = b;
b = r;
}
return a;
}
int main() {
int g = trace_gcd(18, 48);
cout << "gcd(18, 48) = " << g << endl;
unsigned int u = 80000, v = 90000, d = 10000; // 真实 gcd=10000, 真实 lcm=720000
unsigned int bad_lcm = (u * v) / d; // 陷阱:80000*90000=7.2e9 提前溢出 32 位上限
unsigned int ok_lcm = (u / d) * v; // 正确:先整除得 8,再乘 90000 = 720000
cout << "bad_lcm=" << bad_lcm << ", ok_lcm=" << ok_lcm << endl;
return 0;
}分步内存变量变化与辗转推演表
| 执行阶段 | 循环前 a |
循环前 b |
余数 r = a % b |
循环后新 (a, b) |
核心机制剖析 |
|---|---|---|---|---|---|
| Step 1 | 18 |
48 |
18 % 48 = 18 |
(48, 18) |
a < b 时余数等于 a,耗费 1 步自动翻转成大数在前! |
| Step 2 | 48 |
18 |
48 % 18 = 12 |
(18, 12) |
48 = 2 * 18 + 12,规模大幅缩减 |
| Step 3 | 18 |
12 |
18 % 12 = 6 |
(12, 6) |
18 = 1 * 12 + 6(相比 Step 2 的 48 已不足一半) |
| Step 4 | 12 |
6 |
12 % 6 = 0 |
(6, 0) |
余数归零,下一轮 b != 0 为假,退出循环返回 6 |
| LCM 对比 | u = 80000 |
v = 90000 |
u * v 达 7.2e9 |
bad = 290503 |
明明真实答案 720000 远小于 ,先乘却白白溢出报错! |
程序标准输出:
Step 1: a=18, b=48 -> r=18
Step 2: a=48, b=18 -> r=12
Step 3: a=18, b=12 -> r=6
Step 4: a=12, b=6 -> r=0
gcd(18, 48) = 6
bad_lcm=290503, ok_lcm=720000⚡ 三、 考场高频避坑指南(正误辨析)
在 GESP 五级判断题与 CSP-J 考场上,以下三个高频雷区是命题人最偏爱的设陷角度:
❌ 易错点 1:把递归终止条件写成 if (a % b == 0) return b;,遇到 0 瞬间除零崩溃!
- 错误代码:
int gcd(int a, int b) { if (a % b == 0) return b; return gcd(b, a % b); }。 - 为什么错:当题目输入可能包含坐标原点或差值为
0(例如网格斜率向量化简(dx, dy) = (5, 0))时,一旦调用gcd(5, 0),第一句a % b就会立刻执行5 % 0,在底层硬件触发 SIGFPE(除以零浮点异常,直接判 RE 0 分)!相反,标准写法if (b == 0) return a;先拦截了b == 0的情况,根本不会触碰% 0红线,安全返回gcd(5, 0) = 5! - 正确规范:永远以
b == 0作为唯一基准出口;若参数可能为负数(如坐标差dx < 0),传入前先取绝对值gcd(abs(dx), abs(dy)),确保返回的公约数恒为非负数。
❌ 易错点 2:把两数乘积恒等式盲目推广到三个数,误以为 !
- 错误认知:既然两个正整数恒有 ,那么求三个正整数的最小公倍数直接算
a * b * c / gcd(gcd(a, b), c)就行了! - 为什么错:对于三个指数 , 并不等于 (中间那个大小居中的指数被漏掉了)!举一个最简单的反例:取
a = 2, b = 2, c = 2,显然gcd(2, 2, 2) = 2且lcm(2, 2, 2) = 2,左边乘积为2 * 2 = 4,而右边a * b * c = 2 * 2 * 2 = 8,两者根本不相等! - 正确规范:求多个数的 GCD 或 LCM,必须采用两两递推迭代法:
- 多元 GCD:
g = gcd(gcd(a, b), c); - 多元 LCM:先算前两数的最小公倍数
L12 = a / gcd(a, b) * b,再拿L12与第三个数按两数公式求公倍数L123 = L12 / gcd(L12, c) * c!
- 多元 GCD:
❌ 易错点 3:在 C++11/14 赛场环境盲目调用 std::gcd 或轻信 GCC 私货 __gcd!
- 错误操作:不背手写模板,考场直接
#include <numeric>调gcd(a, b),或者#include <algorithm>调__gcd(a, b)。 - 为什么错:
- 标准库的
std::gcd与std::lcm直到 C++17 标准才正式加入!在限定-std=c++11或老版本编译参数的评测机上会直接报编译错误(CE); - 双下划线开头的
__gcd(x, y)属于 GCC 编译器的内部私有扩展函数:一方面它要求两个模板参数类型必须严格一致,写__gcd(12, 18LL)(int与long long混传)会直接模板推导失败 CE;另一方面传入负数时会算出负的“最大公约数”,极易破坏分数化简符号!
- 标准库的
- 正确规范:3 行手写欧几里得函数耗时不到 15 秒,兼容一切 C++ 标准且行为完全可控,考场上一律手写!
📝 四、 真题实战演练与精析(有例题:3 道)
【例题 1 · 单选题】(CSP-J 初赛阅读程序经典题:辗转相除取模次数极值分析)
题目:阅读以下 C++11 函数定义:
int gcd_steps(int a, int b) {
if (b == 0) return 0;
return 1 + gcd_steps(b, a % b);
}若限制输入的两个实参 a, b 均为 [1, 100] 范围内的正整数,在下列四组参数调用中,哪一组使得 gcd_steps(a, b) 的返回值最大(即执行 % 取模运算的次数最多)?( )
- A.
gcd_steps(100, 99) - B.
gcd_steps(96, 64) - C.
gcd_steps(89, 55) - D.
gcd_steps(55, 89)
🔍 答案与逐项排除解析:
- 正确答案:D
- 解析过程:
- 排除 A:最具迷惑性的直觉陷阱!
100和99虽然数值最大且互质,但第 1 步100 % 99 = 1,第 2 步99 % 1 = 0,随后到达b == 0出口,总计仅返回2; - 排除 B:
96 % 64 = 32,64 % 32 = 0,同样只需2次取模; - 对比 C 与 D(斐波那契最坏情况 + 参数翻转加步):注意到
100以内的斐波那契数列依次为1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89。- 对于 C 项
(89, 55):由于89 > 55,每一步商均为1,依次经历(89,55) -> (55,34) -> (34,21) -> (21,13) -> (13,8) -> (8,5) -> (5,3) -> (3,2) -> (2,1) -> (1,0),共执行9次取模; - 对于 D 项
(55, 89):由于传入时满足55 < 89,第 1 次调用执行55 % 89 = 55将状态翻转为gcd_steps(89, 55),白白多花 1 次取模,随后再走完(89, 55)的9次取模,合计达到1 + 9 = 10次(这也是整个[1, 100] x [1, 100]区间内的全局最大值)!故锁定 D。
- 对于 C 项
- 排除 A:最具迷惑性的直觉陷阱!
【例题 2 · 判断题】(GESP 五级数论与类型边界辨析:“先除后乘”能否保住 int 不溢出?)
题目:在 C++11 标准(int 为 32 位有符号整数,上限为 )下,已知两个 int 型正整数变量 a, b 满足 。为了求它们的最小公倍数,只要严格遵守“先除后乘”原则编写语句 int ans = a / gcd(a, b) * b;,就一定不会发生 int 算术溢出。( )
🔍 答案与反例证明:
- 结论:错误(×)
- 辨析证明:
- 厘清“消除中间冗余膨胀”与“最终结果本身超限”的区别:“先除后乘”的作用是保证计算中途的数值绝不会超过最终答案
lcm(a, b)本身(避免出现最终答案小于2e9但a * b提前溢出的冤案);但它无法改变lcm(a, b)本身的数学大小! - 极简反例:取两个互质的
int正整数a = 100000(),b = 99999。显然a, b均远小于 ,且相邻正整数必互质,即gcd(a, b) = 1。此时执行a / gcd(a, b) * b:先除得100000 / 1 = 100000,再乘99999,真实最小公倍数高达 ,远超 32 位int上限 ,照样在* b这一步发生有符号整数溢出! - 正确准则:当
a, b可达 时,其最小公倍数最大可达 量级,不仅要先除后乘,还必须将返回值和乘数提升至 64 位long long(即long long ans = 1LL * (a / gcd(a, b)) * b;)!
- 厘清“消除中间冗余膨胀”与“最终结果本身超限”的区别:“先除后乘”的作用是保证计算中途的数值绝不会超过最终答案
【例题 3 · 微代码实战】(GESP 五级 / CSP-J 复赛常考母题:有理分数序列的防溢出通分求和与最简化简)
题目描述:给定 n()个有理分数 (其中分子 ,分母 )。请精确计算这 n 个分数的累加总和 ,并将最终结果化简为最简分数形式 P/Q 输出(要求分母 Q > 0 且 ;特别地,若累加和恰好为 0,则标准最简形式规定输出为 0/1)。题目保证任意前缀累加和经约分后的最简分子绝对值与最简分母均不超过 。
输入格式:
第一行包含一个正整数 n,表示待累加的分数个数。
接下来 n 行,每行包含两个整数 a_i, b_i,表示第 i 个分数的分子与分母。
输出格式:
输出一行,格式为 P/Q,表示化简后的最简分数总和。
💡 算法建模与防溢出核心要点:
- 读入即约分:题目输入的单个分数如
200000000 / 600000000可能带有高达 的冗余公因数,先用gcd(|a|, b)约成1 / 3可大幅降低分母量级; - LCM 通分防爆:合并当前最简累加和
num / den与新分数a / b时,绝不能直接硬乘分母den * b(最高可达 撑爆long long),而应先求g1 = gcd(den, b),用先除后乘算出最小公分母L = (den / g1) * b,分子对应交叉乘以互质商num * (b / g1) + a * (den / g1); - 零值自动归一魔法:每次相加后立即求
g2 = gcd(|next_num|, L)并同除g2。当分子恰好正负抵消变成0时,由于标准欧几里得函数满足gcd(0, L) == L,执行0 / L = 0与L / L = 1会天然把0/L完美规整为0/1,连特判if都省了!
#include <iostream>
using namespace std;
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
long long my_abs(long long x) {
return x < 0 ? -x : x;
}
int main() {
int n;
cin >> n;
// 初始累加和表示为最简有理分数 0/1
long long num = 0, den = 1;
for (int i = 1; i <= n; i++) {
long long a, b;
cin >> a >> b;
// 1. 先将当前读入的分数自身化为最简,提前消除冗余大公因数
long long g0 = gcd(my_abs(a), b);
a /= g0;
b /= g0;
// 2. 求两分母的最小公倍数作为公分母:严格遵循“先除后乘”防溢出铁律
long long g1 = gcd(den, b);
long long common_den = (den / g1) * b;
long long next_num = num * (b / g1) + a * (den / g1);
// 3. 累加结果再次立即约分;当 next_num 为 0 时 gcd(0, common_den) == common_den,自动归为 0/1
long long g2 = gcd(my_abs(next_num), common_den);
num = next_num / g2;
den = common_den / g2;
}
cout << num << "/" << den << endl;
return 0;
}- 输入样例:
Code5 行
4 200000000 600000000 1 6 -500000000 1000000000 3 8 - 输出样例:
(样例解释:第 1 个分数先约分为Code1 行
3/81/3;加上第 2 个分数1/6时,公分母为lcm(3, 6) = 6,相加得3/6并立即约分为1/2;第 3 个分数先约分为-1/2,与1/2相加分子归零得0/2,经gcd(0, 2) = 2自动归一为标准最简形式0/1;最后加上3/8得最终答案3/8。)
所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI
欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。
猜你想读 · 相关文章推荐
【GESP/CSP考点精讲】GESP四级/五级 / CSP-J 必背:递推 vs 递归——如何手画“递归调用树”秒杀初赛阅读程序题?
为什么在考场上遇到一句看似简单的 return f(n - 1) + f(n - 2);,有些同学在脑子里绕了三层就彻底“死机”,完全算不清函数到底被调用了多少次?为什么仅仅把 cout << n; 放在递归调用语句的前面和后面,打印出来的数字顺序就会发生天翻地覆的“逆...
【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:从 O(2^n) 到 O(n) 的奇迹——重叠子问题与记忆化搜索
为什么一段只有 5 行的斐波那契递归代码 return fib(n - 1) + fib(n - 2);,当输入 n = 10 时瞬间出解,一旦输入 n = 45 就会触发超过 22 亿次函数调用,把评测机死死卡在 TLE(运行超时)?更神奇的是,为什么在不改变递归主体...
【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:分治思想与归并排序(Merge Sort)——顺手秒杀“逆序对”统计
当题目给出的数据规模从 n = 1000 跃升到 n = 10^5 时,无论是冒泡排序、直接插入排序,还是用双重 for 循环暴力枚举统计“逆序对”,运算次数都会瞬间飙升至 (n(n-1)/2) ≈ 5 × 10^9 次,在 1 秒时限面前毫无悬念地触发 TLE(运行超...
OneCoder
一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

