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为什么这个方法成立
- 每次变换保留全部公共因子。
- 非负余数小于除数,循环必终止。
- 终点 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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
gcd(105,252) 需要先手工交换吗?
需要一点提示
第一轮余数是多少?
查看解析与答案
不需要,第一次变为 (252,105),之后自然继续。
b 已为零怎么办?
需要一点提示
循环条件。
查看解析与答案
直接返回 |a|。
如何求一串整数的共同 GCD?
需要一点提示
GCD 可结合。
查看解析与答案
从 0 开始逐个做 result=gcd(result,x),因为 gcd(0,x)=|x|,空集结果可约定为 0。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
CP-Algorithms · 欧几里得与最小公倍数CP-Algorithms · 二进制快速幂