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

从公共因子的定义理解 GCD、互质与约分,再准备更快的取余算法。

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

最大公约数GCD

两个整数的最大公共因子,可用欧几里得算法求解。

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

本课要建立的能力

从公共因子的定义理解 GCD、互质与约分,再准备更快的取余算法。

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

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都不能同时整除从可能上界向下找
候选 618%6=0,12%6=0第一个共同因子
约分 12/18分子分母除以 6,得 2/3比例不变

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

最大方块边长 6;共切 3×2=6 块。

04为什么这个方法成立

  1. 公共因子不可能大于两个正数的较小者。
  2. 从该上界递减枚举,首个同时整除的正整数就是最大公共因子。
  3. 负输入先取绝对值不改变因子集合,零输入按约定单独处理。

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从手算到独立迁移

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

练习 1 · 复现与理解

gcd(8,9) 是多少?

需要一点提示

列公共正因子。

查看解析与答案

1。

练习 2 · 边界与辨析

gcd(−18,12) 呢?

需要一点提示

符号不改变整除关系。

查看解析与答案

6。

练习 3 · 变式与迁移

为什么约分后分子分母互质?

需要一点提示

还能约掉因子就意味着什么?

查看解析与答案

若仍有共同因子 d>1,原分子分母就有比已取 GCD 更大的共同因子,矛盾。

继续深入这个专题

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

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

理解之后,继续递进

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