专题进阶 · 数学算法推荐总顺序 · 第 91 / 148 课

证明取余不改变公共因子集合,并用严格递减保证终止。

先学会这些,再进入本课 最大公约数
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 数学算法

欧几里得算法Euclidean Algorithm

gcd(a,b)=gcd(b,a mod b),不断取余直到第二个数为零。

建议 35 分钟 · 含手算、代码与三层练习

本课要建立的能力

证明取余不改变公共因子集合,并用严格递减保证终止。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

计算 gcd(252,105),能否不枚举 1 到 105 的所有候选?

02一步步得到方法

整除关系在减去倍数后不变

写 a=qb+r。若 d 同时整除 a 和 b,则也整除 r=a−qb;反过来,若 d 整除 b 和 r,就整除 a=qb+r。因此 (a,b) 与 (b,r) 的公共因子集合完全相同。

这得到 gcd(a,b)=gcd(b,a%b)。对非负整数且 b>0,余数 r 满足 0≤r<b,第二项严格减小;最终余数变零,答案就是剩下的非零数。

为什么比反复相减快

减法版本一次只去掉一个 b;取余一次跳过 q 个 b。即使 q 很大也不需要 q 次循环。最慢情况与相邻 Fibonacci 数有关,说明迭代次数按较小数的对数增长。

若要同时得到 ax+by=gcd(a,b) 的系数,可在返回时追踪每次 a=qb+r,这就是扩展欧几里得,模逆元课会使用。

为什么余数保持全部公约数

若 a=qb+r,任何同时整除 a、b 的数也整除 r=a−qb;反过来,同时整除 b、r 的数也整除 a。两组公约数完全相同,因此最大公约数相同。

每步把较大数换成更小的余数,直到余数为0。连续 Fibonacci 数会形成较长的欧几里得链,可用来理解对数级轮数;大整数实际取余成本仍取决于位数。

03把一个小例子完全算清楚

(252,105)。

步骤计算与状态为什么这样做
252=2×105+42变为 (105,42)公共因子集合不变
105=2×42+21变为 (42,21)第二项减小
42=2×21+0变为 (21,0)答案 21

窄屏可左右滑动表格,阅读完整计算与理由。

三次取余就得到答案,不必逐个试除。

04为什么这个方法成立

  1. 每次变换保留全部公共因子。
  2. 非负余数小于除数,循环必终止。
  3. 终点 gcd(a,0)=a,结合不变量得到原输入 GCD。

05把推导翻译成代码

Python · 可独立运行的教学实现

def gcd(a,b):
    a,b = abs(a),abs(b)
    while b:
        a,b = b,a%b
    return a

逐个理解关键决定

a,b = b,a%b
同时赋值使用旧 a、b;若先覆盖 a 再取余会算错。
while b
b 为零时不能再取余,当前 a 即答案。

06时间、空间与实现范围

取余次数 O(log min(|a|,|b|)),辅助变量 O(1)。

这是算术操作次数;超长整数的除法不是常数时间,位复杂度需额外分析。

07改变条件,检查哪里会出错

先执行 a=b,再 b=a%b

a 已丢失原值,余数会变成 b%b=0;使用临时变量或同时赋值。

同时赋值写成会覆盖旧值的顺序赋值

下一步余数必须使用旧 a、b;用临时变量或真正的同时赋值保留它们。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

gcd(105,252) 需要先手工交换吗?

需要一点提示

第一轮余数是多少?

查看解析与答案

不需要,第一次变为 (252,105),之后自然继续。

练习 2 · 边界与辨析

b 已为零怎么办?

需要一点提示

循环条件。

查看解析与答案

直接返回 |a|。

练习 3 · 变式与迁移

如何求一串整数的共同 GCD?

需要一点提示

GCD 可结合。

查看解析与答案

从 0 开始逐个做 result=gcd(result,x),因为 gcd(0,x)=|x|,空集结果可约定为 0。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

CP-Algorithms · 欧几里得与最小公倍数CP-Algorithms · 二进制快速幂

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。