01先把问题说具体
长 18、宽 12 的矩形要切成等大的正方形且没有剩余,最大边长是多少?
02一步步得到方法
把几何问题变成整除问题
边长 d 必须同时整除 18 和 12,所有可行 d 是两数公共因子。18 的正因子为 1、2、3、6、9、18,12 的为 1、2、3、4、6、12,所以最大公共因子是 6。
GCD 通常取非负结果,gcd(a,0)=|a|;gcd(0,0) 常在程序中约定为 0,虽然正公共因子的最大值在数学定义中不适用。要明确零值约定,避免循环边界出错。
互质不要求两个数都是质数
gcd(a,b)=1 称为互质,例如 8 与 9 都是合数却互质。把分子分母同时除以 GCD,就得到最简分数;之后最小公倍数与模逆元也会依赖这个概念。
本课先用枚举因子给出容易核对的定义实现,下一课欧几里得算法再把寻找速度从线性量级缩短到对数次数取余。
整除关系比试除所有数更有力量
最大公约数是能同时整除两个整数的最大非负整数。它描述两个长度共同的最小刻度,也用于约分;例如18和24的所有公约数正好是6的约数。
特殊输入先约定:gcd(a,0)=|a|,因为任何 a 的约数都整除0;gcd(0,0) 通常在程序库中返回0。数学定义和接口约定要区分,负号不影响公约数大小。
03把一个小例子完全算清楚
a=18,b=12。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 候选 12..7 | 都不能同时整除 | 从可能上界向下找 |
| 候选 6 | 18%6=0,12%6=0 | 第一个共同因子 |
| 约分 12/18 | 分子分母除以 6,得 2/3 | 比例不变 |
窄屏可左右滑动表格,阅读完整计算与理由。
最大方块边长 6;共切 3×2=6 块。
04为什么这个方法成立
- 公共因子不可能大于两个正数的较小者。
- 从该上界递减枚举,首个同时整除的正整数就是最大公共因子。
- 负输入先取绝对值不改变因子集合,零输入按约定单独处理。
05把推导翻译成代码
Python · 可独立运行的教学实现
def gcd_by_definition(a,b):
a,b = abs(a),abs(b)
if a == 0 or b == 0:
return max(a,b)
for d in range(min(a,b),0,-1):
if a%d == 0 and b%d == 0:
return d逐个理解关键决定
range(min(a,b),0,-1)- 降序使第一次命中即可返回最大值。
return max(a,b)- 一边为零时另一边就是 GCD,双方零则返回约定值 0。
06时间、空间与实现范围
固定宽度算术模型下最坏 O(min(|a|,|b|)) 次整除,辅助空间 O(1)。
大整数不适合逐因子枚举,此代码是定义基线,后续应使用欧几里得算法。
07改变条件,检查哪里会出错
互质就说明两个数都为质数
8 与 9 是反例;互质描述两个数之间的关系。
用连续减法处理极不平衡的大数
重复减法可能非常慢,取余一次可以跳过多次相减。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
gcd(8,9) 是多少?
需要一点提示
列公共正因子。
查看解析与答案
1。
gcd(−18,12) 呢?
需要一点提示
符号不改变整除关系。
查看解析与答案
6。
为什么约分后分子分母互质?
需要一点提示
还能约掉因子就意味着什么?
查看解析与答案
若仍有共同因子 d>1,原分子分母就有比已取 GCD 更大的共同因子,矛盾。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
CP-Algorithms · 欧几里得与最小公倍数CP-Algorithms · 二进制快速幂