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

从质因子指数解释 GCD 与 LCM 乘积关系,安全处理零与溢出。

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

最小公倍数LCM

利用 lcm(a,b)=

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

本课要建立的能力

从质因子指数解释 GCD 与 LCM 乘积关系,安全处理零与溢出。

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

01先把问题说具体

两个周期分别为 12 分钟和 18 分钟,首次同时再次发生是在多久之后?

02一步步得到方法

公共倍数与公共因子方向相反

公倍数必须同时被两数整除,最小正公倍数称为 LCM。12=2²×3,18=2×3²,LCM 取各质因子的较大指数,得到 2²×3²=36;GCD 取较小指数得到 6。

对每个质因子,最大指数加最小指数等于原两个指数之和,所以 gcd(a,b)·lcm(a,b)=|ab|。无需实际分解质因数也能利用这条关系。

先除后乘降低中间值

计算 |a/gcd(a,b)×b|,先做整除再乘,避免 a*b 的中间值比最终答案更早溢出。最终 LCM 本身仍可能超出固定宽度范围,需要按应用检测。

程序通常约定只要一边为 0,LCM 返回 0;特别是 (0,0) 必须在除以 gcd 前处理,否则分母为 0。周期问题还要求周期为正,不能把程序的零约定直接当作物理周期解释。

先除后乘降低中间规模

对正整数 a、b,按素因子指数看,gcd 取每个指数的最小值,lcm 取最大值,两者指数和等于 a、b 指数之和,因此 gcd(a,b)×lcm(a,b)=ab。

实现用 |a/gcd(a,b)×b|,先除能减小中间值,在固定宽度整数中尤其重要;但最终最小公倍数本身也可能超出表示范围,先除并非万能防溢出。

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

a=12,b=18。

步骤计算与状态为什么这样做
求 GCD18%12=6,12%6=0公共因子 6
先约去12//6=2减小中间数
再相乘2×18=36两个周期的共同倍数

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

36/12=3,36/18=2,两个事件分别经历 3 次与 2 次周期后重合。

04为什么这个方法成立

  1. GCD 与 LCM 分别取质因子的最小与最大指数。
  2. 两者相乘恢复 |ab| 的各质因子总指数。
  3. 因此除去 GCD 后再乘得到最小公共倍数,符号取绝对值。

05把推导翻译成代码

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

from math import gcd
def lcm(a,b):
    if a == 0 or b == 0:
        return 0
    return abs((a//gcd(a,b))*b)

逐个理解关键决定

a//gcd(a,b)
已知整除,使用整数除法,不要引入浮点误差。
if a == 0 or b == 0
先处理零,避免 (0,0) 的除零。

06时间、空间与实现范围

主要成本是一次 GCD,算术操作次数 O(log min(|a|,|b|)),其余常数次乘除。

大整数乘法成本与位数有关;C++ 等固定宽度实现需检查最终乘积范围。

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

先转浮点做 a/gcd 再转回整数

大整数可能丢精度,应始终使用整除。

零输入仍直接除以 gcd(0,0)

通常约定任一输入为0时 lcm 为0,应先处理以避免除零。

08从手算到独立迁移

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

练习 1 · 复现与理解

lcm(8,9) 是多少?

需要一点提示

两数互质。

查看解析与答案

72。

练习 2 · 边界与辨析

lcm(4,12) 为什么是 12?

需要一点提示

一个数已是另一个倍数。

查看解析与答案

最小能同时被 4 与 12 整除的正数就是 12。

练习 3 · 变式与迁移

如何求多个周期共同重复时间?

需要一点提示

LCM 也可逐次合并。

查看解析与答案

从 1 开始折叠 lcm,注意结果可能快速增大,并且实际时间单位必须一致。

继续深入这个专题

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

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

理解之后,继续递进

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