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。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 求 GCD | 18%12=6,12%6=0 | 公共因子 6 |
| 先约去 | 12//6=2 | 减小中间数 |
| 再相乘 | 2×18=36 | 两个周期的共同倍数 |
窄屏可左右滑动表格,阅读完整计算与理由。
36/12=3,36/18=2,两个事件分别经历 3 次与 2 次周期后重合。
04为什么这个方法成立
- GCD 与 LCM 分别取质因子的最小与最大指数。
- 两者相乘恢复 |ab| 的各质因子总指数。
- 因此除去 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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
lcm(8,9) 是多少?
需要一点提示
两数互质。
查看解析与答案
72。
lcm(4,12) 为什么是 12?
需要一点提示
一个数已是另一个倍数。
查看解析与答案
最小能同时被 4 与 12 整除的正数就是 12。
如何求多个周期共同重复时间?
需要一点提示
LCM 也可逐次合并。
查看解析与答案
从 1 开始折叠 lcm,注意结果可能快速增大,并且实际时间单位必须一致。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
CP-Algorithms · 欧几里得与最小公倍数CP-Algorithms · 二进制快速幂