1. 从“模板”说起为什么我们需要它如果你写过一段时间的代码尤其是处理过算法题或者一些基础的数学计算你大概率会和我有一样的感受有些代码片段你会在不同的项目、不同的题目里一遍又一遍地重复书写。比如判断一个数是不是素数比如计算两个数的最大公约数GCD和最小公倍数LCM。每次遇到你都得停下来想一想辗转相除法的边界条件是什么最小公倍数和最大公约数之间那个简洁的公式lcm(a, b) a * b / gcd(a, b)会不会因为溢出而出问题这就是“模板”的价值所在。它不是一个死板的、必须照抄的框架而是一个经过实战检验、考虑了各种边界情况和性能优化的“代码工具箱”。当你把gcd和lcm这样的函数封装成可靠的模板你节省的不仅仅是敲键盘的时间更重要的是节省了宝贵的、用于思考核心逻辑的脑力。你不会再在基础的数学运算上犯低级错误可以把全部注意力集中在问题本身的建模和算法设计上。今天我们就来深入聊聊这两个最基础也最重要的数论模板——最大公约数和最小公倍数看看如何把它们写得既正确又高效并理解它们在不同场景下的应用。2. 最大公约数不止于“辗转相除”最大公约数顾名思义就是两个或多个整数共有约数中最大的一个。它在简化分数、计算最简整数比、解决“均分”问题比如把一堆物品平均分给几个人且没有剩余时至关重要。2.1 核心算法欧几里得算法及其优化最广为人知的方法是欧几里得算法也叫辗转相除法。它的原理基于一个核心定理gcd(a, b) gcd(b, a % b)。直到余数为0时此时的除数就是最大公约数。一个最朴素的递归实现看起来是这样的def gcd_naive(a, b): if b 0: return a return gcd_naive(b, a % b)这个实现清晰易懂但对于非常大的整数或者极端情况如b远大于a递归深度可能是个问题。我们可以将其改为迭代版本这也是更常见的模板形式def gcd_iterative(a, b): while b: a, b b, a % b return a这里有一个关键的细节while b:这个循环条件。当b为0时循环结束此时a的值就是最大公约数。这个写法非常Pythonic。然而我们还能更进一步。对于现代CPU取模运算%比减法运算要慢。对于某些特定场景或者追求极致的性能时可以使用更相减损术的变种但通常使用内置函数是最好的选择。实操心得一直接使用math.gcd在Python 3.5中标准库math模块提供了gcd函数它用C语言实现经过高度优化是计算两个数最大公约数的最佳选择。除非你有非常特殊的定制需求比如需要同时计算系数x, y的扩展欧几里得算法否则永远应该优先使用math.gcd。import math result math.gcd(12, 18) # 返回 62.2 处理多个数的最大公约数问题很少只涉及两个数。当需要计算一个列表比如[12, 18, 24]所有元素的最大公约数时原理是gcd(a, b, c) gcd(gcd(a, b), c)。我们可以利用functools.reduce函数优雅地实现。reduce函数会对序列中的元素连续应用某个函数这里是gcd逐步将序列“缩减”为单个值。import math from functools import reduce numbers [12, 18, 24] gcd_of_all reduce(math.gcd, numbers) # 返回 6它的执行过程相当于math.gcd(math.gcd(12, 18), 24)。这是一个非常实用且地道的Python模式务必掌握。2.3 边界情况与注意事项零的处理根据定义任何非零整数与0的最大公约数是这个非零整数本身。math.gcd(0, 5)返回5math.gcd(0, 0)通常定义为0。我们的迭代模板while b:也能正确处理b0的情况循环直接跳过返回a。负数最大公约数通常定义为正数。math.gcd会自动处理负号返回正数结果。例如math.gcd(-12, 18)返回6。如果你自己实现记得在最后返回绝对值abs(a)。大数与性能对于超大的整数比如几百位math.gcd内部使用的是高效的二进制算法或更优的实现远比我们自己写的Python循环要快。这是使用标准库的另一个重要理由。3. 最小公倍数与最大公约数的“孪生”关系最小公倍数是指两个或多个整数公有的倍数中最小的一个。它在处理“周期”问题时非常有用比如两个事件同时发生求下一次同时发生的时间或者需要找到一个能同时被几个数整除的最小整数。3.1 利用GCD计算LCM的公式与陷阱计算最小公倍数最常用的公式是lcm(a, b) a * b / gcd(a, b)这个公式非常优美它将LCM的计算转化为了我们已经掌握的GCD计算。在Python中一个直接的实现是def lcm_basic(a, b): return a * b // math.gcd(a, b)注意这里使用整数除法//因为a * b一定能被gcd(a, b)整除结果必然是整数。但是这里隐藏着一个巨大的陷阱整数溢出。在C或Java等语言中a * b可能会超过整型如int的范围导致溢出即使最终结果本应在范围内。因此更安全的写法是先除后乘lcm(a, b) a / gcd(a, b) * b由于除法先进行数值会先变小通常能避免溢出问题。在Python中大整数是自动处理的理论上不会溢出。但先除后乘是一个非常好的习惯它使你的代码逻辑更清晰且更容易移植到其他语言。因此我们的标准模板应该是def lcm(a, b): return a // math.gcd(a, b) * b3.2 多个数的最小公倍数计算和GCD类似多个数的LCM也可以通过迭代计算得到lcm(a, b, c) lcm(lcm(a, b), c)。同样我们可以用reduce来实现from functools import reduce import math def lcm(a, b): return a // math.gcd(a, b) * b numbers [12, 18, 24] lcm_of_all reduce(lcm, numbers) # 返回 72实操心得二将LCM和GCD模板函数化我强烈建议在你的代码工具箱可以是一个单独的utils.py文件里固定下这两个函数import math from functools import reduce def gcd(*args): 计算任意多个整数的最大公约数。 if len(args) 0: return 0 if len(args) 1: return abs(args[0]) return reduce(math.gcd, args) def lcm(*args): 计算任意多个整数的最小公倍数。 if len(args) 0: return 1 # 通常定义空集的lcm为1 result 1 for num in args: result result // math.gcd(result, num) * num return result # 或者使用reduce的版本 def lcm_reduce(*args): if len(args) 0: return 1 return reduce(lambda x, y: x // math.gcd(x, y) * y, args, 1)这样你就可以用gcd(12, 18, 24)和lcm(12, 18, 24)这样非常直观的方式来调用了。*args的用法让函数可以接受任意数量的参数非常灵活。4. 实战场景解析模板如何解决具体问题掌握了可靠的模板我们来看看它们如何应用于具体的编程和算法问题中。4.1 场景一分数计算与化简这是最直接的应用。例如我们要实现一个分数类Fraction其核心操作加法、减法、乘法、除法最后都需要化简为最简形式。化简就是分子分母同时除以它们的最大公约数。class Fraction: def __init__(self, numerator, denominator): if denominator 0: raise ValueError(分母不能为零) g math.gcd(numerator, denominator) # 化简并确保分母为正 self.numer numerator // g self.denom denominator // g if self.denom 0: # 将负号统一放到分子 self.numer, self.denom -self.numer, -self.denom def __add__(self, other): # 通分分母为两个分母的最小公倍数 common_denom lcm(self.denom, other.denom) new_numer self.numer * (common_denom // self.denom) other.numer * (common_denom // other.denom) return Fraction(new_numer, common_denom) def __str__(self): return f{self.numer}/{self.denom} # 使用 f1 Fraction(1, 6) f2 Fraction(1, 4) print(f1 f2) # 输出 5/12 已经是最简形式在这个例子中GCD用于构造时的即时化简LCM用于加法运算时的通分。没有这两个模板分数运算的代码会变得冗长且容易出错。4.2 场景二解决“相遇”周期问题这类问题通常描述为A事件每a天发生一次B事件每b天发生一次它们今天同时发生问至少多少天后会再次同时发生答案就是lcm(a, b)。变体问题三条环形跑道运动员甲、乙、丙分别每5分钟、6分钟、10分钟跑完一圈从同一起点同时出发问至少多少分钟后三人在起点再次相遇 解这就是求5610的最小公倍数。lcm(5, 6, 10) 30。30分钟后三人再次在起点相遇。在代码中这通常是一个简单的函数调用meeting_time lcm(cycle_a, cycle_b, cycle_c)4.3 场景三在算法竞赛中的应用在许多算法题中GCD和LCM是隐藏的关键。例如判断两点之间是否存在整数点在坐标系中点(x1, y1)和点(x2, y2)问线段上除端点外有多少个整数坐标点这等价于求gcd(abs(x1-x2), abs(y1-y2)) - 1。因为步长必须同时整除横纵坐标的差值。处理比例与缩放需要将一组整数按比例缩放且保持为整数通常需要用到LCM来找到公共的缩放基数。数论与模运算扩展欧几里得算法基于GCD是求解线性同余方程a*x ≡ b (mod m)和乘法逆元的基础这在密码学、组合数学中非常重要。一个综合案例LeetCode上一道经典题目“水壶问题”。你有两个容量分别为x升和y升的水壶能否通过倒水、填满、清空操作得到恰好z升水这个问题的数学本质是z是否是x和y的最大公约数的倍数即z % gcd(x, y) 0。如果你不知道这个结论可能会去尝试复杂的搜索但知道了GCD模板问题就迎刃而解。def can_measure_water(jug1_capacity, jug2_capacity, target_capacity): if target_capacity jug1_capacity jug2_capacity: return False if target_capacity 0: return True return target_capacity % math.gcd(jug1_capacity, jug2_capacity) 05. 高级话题与性能考量5.1 扩展欧几里得算法标准的GCD算法只返回值。扩展欧几里得算法在计算gcd(a, b)的同时还能找到一组整数x, y使得a*x b*y gcd(a, b)成立。这个等式被称为贝祖定理。这个算法在求解模线性方程、计算模逆元时不可或缺。它的模板稍微复杂一些def extended_gcd(a, b): 返回一个三元组 (g, x, y)使得 a*x b*y g gcd(a, b) if b 0: return (a, 1, 0) else: g, x1, y1 extended_gcd(b, a % b) # 根据递归结果回溯计算 x, y x y1 y x1 - (a // b) * y1 return (g, x, y) # 示例求解 35x 15y gcd(35, 15) 5 g, x, y extended_gcd(35, 15) print(f{g} 35*({x}) 15*({y})) # 输出5 35*(1) 15*(-2)理解这个算法的推导需要一些数论基础但将其作为模板记住在需要时直接使用能解决一大类问题。5.2 二进制GCD算法对于特别大的整数或者在没有硬件除法指令的嵌入式环境中二进制GCD算法Stein算法可能更高效。它的核心思想是利用移位相当于除以2和减法来代替耗时的取模运算。基本步骤是如果a和b都是偶数gcd(a,b) 2 * gcd(a/2, b/2)。如果a是偶数b是奇数gcd(a,b) gcd(a/2, b)。如果a和b都是奇数gcd(a,b) gcd(|a-b|, min(a,b))。重复直到其中一个为0。Python的math.gcd内部可能已经采用了类似或更优的算法。我们自己实现一个有助于理解def binary_gcd(a, b): if a 0: return b if b 0: return a # 找出2的公共幂次 shift 0 while ((a | b) 1) 0: # 当a和b都是偶数时 a 1 b 1 shift 1 while (a 1) 0: # 去掉a中所有的因子2 a 1 while b ! 0: while (b 1) 0: # 去掉b中所有的因子2 b 1 # 现在a和b都是奇数用更相减损术 if a b: a, b b, a b b - a return a shift # 乘回2的公共幂次性能对比对于一般的整数math.gcd是最优选择。二进制GCD在特定场景或自定义大整数库中有其优势。对于绝大多数应用我们无需自己实现。5.3 与质因数分解的关系从定义上看GCD和LCM也可以通过质因数分解来求将每个数分解为质因数的幂次形式GCD取每个质因数的最小指数LCM取每个质因数的最大指数。例如12 2^2 * 3^118 2^1 * 3^2gcd(12, 18) 2^min(2,1) * 3^min(1,2) 2^1 * 3^1 6lcm(12, 18) 2^max(2,1) * 3^max(1,2) 2^2 * 3^2 36这种方法在数学上很直观但在编程中效率远低于欧几里得算法因为质因数分解本身是一个更困难的问题。所以gcd(a,b) a*b / lcm(a,b)这个公式在理论推导中常用但实际计算中我们总是用欧几里得算法求GCD再用它来求LCM。6. 构建你自己的数学工具库最后我想分享一下我个人组织这些“模板”或“工具函数”的习惯。我不会在每次做题时都重新敲一遍gcd和lcm而是会维护一个自己的math_utils.py文件。这个文件里不仅包含今天讲的GCD和LCM还有质数判断、快速幂、组合数计算、欧拉函数等常用数论函数。# math_utils.py import math from functools import reduce def gcd(*args): 计算任意多个整数的最大公约数。 if len(args) 0: return 0 return reduce(math.gcd, args) def lcm(*args): 计算任意多个整数的最小公倍数。 if len(args) 0: return 1 return reduce(lambda x, y: x // math.gcd(x, y) * y, args, 1) def is_prime(n): 判断一个正整数是否为质数。 if n 2: return False if n % 2 0: return n 2 if n % 3 0: return n 3 i 5 w 2 while i * i n: if n % i 0: return False i w w 6 - w # 在5,7,11,13,...之间交替 return True def fast_pow(base, exp, modNone): 快速幂算法支持取模。 result 1 while exp 0: if exp 1: # 如果指数是奇数 result result * base if mod is not None: result % mod base base * base if mod is not None: base % mod exp 1 # 指数右移一位除以2 return result # ... 其他工具函数然后在需要用的脚本或项目中直接from math_utils import gcd, lcm即可。这种积累会让你在解决复杂问题时更加得心应手因为你不需要在基础构件上花费任何额外精力。回到最初的标题“最小公倍数模板最大公约数模板”它们绝不仅仅是两行代码。它们是经过抽象和验证的思维工具是构建更复杂解决方案的基石。理解其原理掌握其实现牢记其陷阱如LCM的溢出问题并熟练应用于各种场景这便是一个合格程序员在基础数论方面应有的素养。下次当你遇到需要求公约数或公倍数的问题时希望你能自信地调用你的“模板”而不是从头开始推导。 最大公约数与最小公倍数：原理、实现与实战应用
1. 从“模板”说起为什么我们需要它如果你写过一段时间的代码尤其是处理过算法题或者一些基础的数学计算你大概率会和我有一样的感受有些代码片段你会在不同的项目、不同的题目里一遍又一遍地重复书写。比如判断一个数是不是素数比如计算两个数的最大公约数GCD和最小公倍数LCM。每次遇到你都得停下来想一想辗转相除法的边界条件是什么最小公倍数和最大公约数之间那个简洁的公式lcm(a, b) a * b / gcd(a, b)会不会因为溢出而出问题这就是“模板”的价值所在。它不是一个死板的、必须照抄的框架而是一个经过实战检验、考虑了各种边界情况和性能优化的“代码工具箱”。当你把gcd和lcm这样的函数封装成可靠的模板你节省的不仅仅是敲键盘的时间更重要的是节省了宝贵的、用于思考核心逻辑的脑力。你不会再在基础的数学运算上犯低级错误可以把全部注意力集中在问题本身的建模和算法设计上。今天我们就来深入聊聊这两个最基础也最重要的数论模板——最大公约数和最小公倍数看看如何把它们写得既正确又高效并理解它们在不同场景下的应用。2. 最大公约数不止于“辗转相除”最大公约数顾名思义就是两个或多个整数共有约数中最大的一个。它在简化分数、计算最简整数比、解决“均分”问题比如把一堆物品平均分给几个人且没有剩余时至关重要。2.1 核心算法欧几里得算法及其优化最广为人知的方法是欧几里得算法也叫辗转相除法。它的原理基于一个核心定理gcd(a, b) gcd(b, a % b)。直到余数为0时此时的除数就是最大公约数。一个最朴素的递归实现看起来是这样的def gcd_naive(a, b): if b 0: return a return gcd_naive(b, a % b)这个实现清晰易懂但对于非常大的整数或者极端情况如b远大于a递归深度可能是个问题。我们可以将其改为迭代版本这也是更常见的模板形式def gcd_iterative(a, b): while b: a, b b, a % b return a这里有一个关键的细节while b:这个循环条件。当b为0时循环结束此时a的值就是最大公约数。这个写法非常Pythonic。然而我们还能更进一步。对于现代CPU取模运算%比减法运算要慢。对于某些特定场景或者追求极致的性能时可以使用更相减损术的变种但通常使用内置函数是最好的选择。实操心得一直接使用math.gcd在Python 3.5中标准库math模块提供了gcd函数它用C语言实现经过高度优化是计算两个数最大公约数的最佳选择。除非你有非常特殊的定制需求比如需要同时计算系数x, y的扩展欧几里得算法否则永远应该优先使用math.gcd。import math result math.gcd(12, 18) # 返回 62.2 处理多个数的最大公约数问题很少只涉及两个数。当需要计算一个列表比如[12, 18, 24]所有元素的最大公约数时原理是gcd(a, b, c) gcd(gcd(a, b), c)。我们可以利用functools.reduce函数优雅地实现。reduce函数会对序列中的元素连续应用某个函数这里是gcd逐步将序列“缩减”为单个值。import math from functools import reduce numbers [12, 18, 24] gcd_of_all reduce(math.gcd, numbers) # 返回 6它的执行过程相当于math.gcd(math.gcd(12, 18), 24)。这是一个非常实用且地道的Python模式务必掌握。2.3 边界情况与注意事项零的处理根据定义任何非零整数与0的最大公约数是这个非零整数本身。math.gcd(0, 5)返回5math.gcd(0, 0)通常定义为0。我们的迭代模板while b:也能正确处理b0的情况循环直接跳过返回a。负数最大公约数通常定义为正数。math.gcd会自动处理负号返回正数结果。例如math.gcd(-12, 18)返回6。如果你自己实现记得在最后返回绝对值abs(a)。大数与性能对于超大的整数比如几百位math.gcd内部使用的是高效的二进制算法或更优的实现远比我们自己写的Python循环要快。这是使用标准库的另一个重要理由。3. 最小公倍数与最大公约数的“孪生”关系最小公倍数是指两个或多个整数公有的倍数中最小的一个。它在处理“周期”问题时非常有用比如两个事件同时发生求下一次同时发生的时间或者需要找到一个能同时被几个数整除的最小整数。3.1 利用GCD计算LCM的公式与陷阱计算最小公倍数最常用的公式是lcm(a, b) a * b / gcd(a, b)这个公式非常优美它将LCM的计算转化为了我们已经掌握的GCD计算。在Python中一个直接的实现是def lcm_basic(a, b): return a * b // math.gcd(a, b)注意这里使用整数除法//因为a * b一定能被gcd(a, b)整除结果必然是整数。但是这里隐藏着一个巨大的陷阱整数溢出。在C或Java等语言中a * b可能会超过整型如int的范围导致溢出即使最终结果本应在范围内。因此更安全的写法是先除后乘lcm(a, b) a / gcd(a, b) * b由于除法先进行数值会先变小通常能避免溢出问题。在Python中大整数是自动处理的理论上不会溢出。但先除后乘是一个非常好的习惯它使你的代码逻辑更清晰且更容易移植到其他语言。因此我们的标准模板应该是def lcm(a, b): return a // math.gcd(a, b) * b3.2 多个数的最小公倍数计算和GCD类似多个数的LCM也可以通过迭代计算得到lcm(a, b, c) lcm(lcm(a, b), c)。同样我们可以用reduce来实现from functools import reduce import math def lcm(a, b): return a // math.gcd(a, b) * b numbers [12, 18, 24] lcm_of_all reduce(lcm, numbers) # 返回 72实操心得二将LCM和GCD模板函数化我强烈建议在你的代码工具箱可以是一个单独的utils.py文件里固定下这两个函数import math from functools import reduce def gcd(*args): 计算任意多个整数的最大公约数。 if len(args) 0: return 0 if len(args) 1: return abs(args[0]) return reduce(math.gcd, args) def lcm(*args): 计算任意多个整数的最小公倍数。 if len(args) 0: return 1 # 通常定义空集的lcm为1 result 1 for num in args: result result // math.gcd(result, num) * num return result # 或者使用reduce的版本 def lcm_reduce(*args): if len(args) 0: return 1 return reduce(lambda x, y: x // math.gcd(x, y) * y, args, 1)这样你就可以用gcd(12, 18, 24)和lcm(12, 18, 24)这样非常直观的方式来调用了。*args的用法让函数可以接受任意数量的参数非常灵活。4. 实战场景解析模板如何解决具体问题掌握了可靠的模板我们来看看它们如何应用于具体的编程和算法问题中。4.1 场景一分数计算与化简这是最直接的应用。例如我们要实现一个分数类Fraction其核心操作加法、减法、乘法、除法最后都需要化简为最简形式。化简就是分子分母同时除以它们的最大公约数。class Fraction: def __init__(self, numerator, denominator): if denominator 0: raise ValueError(分母不能为零) g math.gcd(numerator, denominator) # 化简并确保分母为正 self.numer numerator // g self.denom denominator // g if self.denom 0: # 将负号统一放到分子 self.numer, self.denom -self.numer, -self.denom def __add__(self, other): # 通分分母为两个分母的最小公倍数 common_denom lcm(self.denom, other.denom) new_numer self.numer * (common_denom // self.denom) other.numer * (common_denom // other.denom) return Fraction(new_numer, common_denom) def __str__(self): return f{self.numer}/{self.denom} # 使用 f1 Fraction(1, 6) f2 Fraction(1, 4) print(f1 f2) # 输出 5/12 已经是最简形式在这个例子中GCD用于构造时的即时化简LCM用于加法运算时的通分。没有这两个模板分数运算的代码会变得冗长且容易出错。4.2 场景二解决“相遇”周期问题这类问题通常描述为A事件每a天发生一次B事件每b天发生一次它们今天同时发生问至少多少天后会再次同时发生答案就是lcm(a, b)。变体问题三条环形跑道运动员甲、乙、丙分别每5分钟、6分钟、10分钟跑完一圈从同一起点同时出发问至少多少分钟后三人在起点再次相遇 解这就是求5610的最小公倍数。lcm(5, 6, 10) 30。30分钟后三人再次在起点相遇。在代码中这通常是一个简单的函数调用meeting_time lcm(cycle_a, cycle_b, cycle_c)4.3 场景三在算法竞赛中的应用在许多算法题中GCD和LCM是隐藏的关键。例如判断两点之间是否存在整数点在坐标系中点(x1, y1)和点(x2, y2)问线段上除端点外有多少个整数坐标点这等价于求gcd(abs(x1-x2), abs(y1-y2)) - 1。因为步长必须同时整除横纵坐标的差值。处理比例与缩放需要将一组整数按比例缩放且保持为整数通常需要用到LCM来找到公共的缩放基数。数论与模运算扩展欧几里得算法基于GCD是求解线性同余方程a*x ≡ b (mod m)和乘法逆元的基础这在密码学、组合数学中非常重要。一个综合案例LeetCode上一道经典题目“水壶问题”。你有两个容量分别为x升和y升的水壶能否通过倒水、填满、清空操作得到恰好z升水这个问题的数学本质是z是否是x和y的最大公约数的倍数即z % gcd(x, y) 0。如果你不知道这个结论可能会去尝试复杂的搜索但知道了GCD模板问题就迎刃而解。def can_measure_water(jug1_capacity, jug2_capacity, target_capacity): if target_capacity jug1_capacity jug2_capacity: return False if target_capacity 0: return True return target_capacity % math.gcd(jug1_capacity, jug2_capacity) 05. 高级话题与性能考量5.1 扩展欧几里得算法标准的GCD算法只返回值。扩展欧几里得算法在计算gcd(a, b)的同时还能找到一组整数x, y使得a*x b*y gcd(a, b)成立。这个等式被称为贝祖定理。这个算法在求解模线性方程、计算模逆元时不可或缺。它的模板稍微复杂一些def extended_gcd(a, b): 返回一个三元组 (g, x, y)使得 a*x b*y g gcd(a, b) if b 0: return (a, 1, 0) else: g, x1, y1 extended_gcd(b, a % b) # 根据递归结果回溯计算 x, y x y1 y x1 - (a // b) * y1 return (g, x, y) # 示例求解 35x 15y gcd(35, 15) 5 g, x, y extended_gcd(35, 15) print(f{g} 35*({x}) 15*({y})) # 输出5 35*(1) 15*(-2)理解这个算法的推导需要一些数论基础但将其作为模板记住在需要时直接使用能解决一大类问题。5.2 二进制GCD算法对于特别大的整数或者在没有硬件除法指令的嵌入式环境中二进制GCD算法Stein算法可能更高效。它的核心思想是利用移位相当于除以2和减法来代替耗时的取模运算。基本步骤是如果a和b都是偶数gcd(a,b) 2 * gcd(a/2, b/2)。如果a是偶数b是奇数gcd(a,b) gcd(a/2, b)。如果a和b都是奇数gcd(a,b) gcd(|a-b|, min(a,b))。重复直到其中一个为0。Python的math.gcd内部可能已经采用了类似或更优的算法。我们自己实现一个有助于理解def binary_gcd(a, b): if a 0: return b if b 0: return a # 找出2的公共幂次 shift 0 while ((a | b) 1) 0: # 当a和b都是偶数时 a 1 b 1 shift 1 while (a 1) 0: # 去掉a中所有的因子2 a 1 while b ! 0: while (b 1) 0: # 去掉b中所有的因子2 b 1 # 现在a和b都是奇数用更相减损术 if a b: a, b b, a b b - a return a shift # 乘回2的公共幂次性能对比对于一般的整数math.gcd是最优选择。二进制GCD在特定场景或自定义大整数库中有其优势。对于绝大多数应用我们无需自己实现。5.3 与质因数分解的关系从定义上看GCD和LCM也可以通过质因数分解来求将每个数分解为质因数的幂次形式GCD取每个质因数的最小指数LCM取每个质因数的最大指数。例如12 2^2 * 3^118 2^1 * 3^2gcd(12, 18) 2^min(2,1) * 3^min(1,2) 2^1 * 3^1 6lcm(12, 18) 2^max(2,1) * 3^max(1,2) 2^2 * 3^2 36这种方法在数学上很直观但在编程中效率远低于欧几里得算法因为质因数分解本身是一个更困难的问题。所以gcd(a,b) a*b / lcm(a,b)这个公式在理论推导中常用但实际计算中我们总是用欧几里得算法求GCD再用它来求LCM。6. 构建你自己的数学工具库最后我想分享一下我个人组织这些“模板”或“工具函数”的习惯。我不会在每次做题时都重新敲一遍gcd和lcm而是会维护一个自己的math_utils.py文件。这个文件里不仅包含今天讲的GCD和LCM还有质数判断、快速幂、组合数计算、欧拉函数等常用数论函数。# math_utils.py import math from functools import reduce def gcd(*args): 计算任意多个整数的最大公约数。 if len(args) 0: return 0 return reduce(math.gcd, args) def lcm(*args): 计算任意多个整数的最小公倍数。 if len(args) 0: return 1 return reduce(lambda x, y: x // math.gcd(x, y) * y, args, 1) def is_prime(n): 判断一个正整数是否为质数。 if n 2: return False if n % 2 0: return n 2 if n % 3 0: return n 3 i 5 w 2 while i * i n: if n % i 0: return False i w w 6 - w # 在5,7,11,13,...之间交替 return True def fast_pow(base, exp, modNone): 快速幂算法支持取模。 result 1 while exp 0: if exp 1: # 如果指数是奇数 result result * base if mod is not None: result % mod base base * base if mod is not None: base % mod exp 1 # 指数右移一位除以2 return result # ... 其他工具函数然后在需要用的脚本或项目中直接from math_utils import gcd, lcm即可。这种积累会让你在解决复杂问题时更加得心应手因为你不需要在基础构件上花费任何额外精力。回到最初的标题“最小公倍数模板最大公约数模板”它们绝不仅仅是两行代码。它们是经过抽象和验证的思维工具是构建更复杂解决方案的基石。理解其原理掌握其实现牢记其陷阱如LCM的溢出问题并熟练应用于各种场景这便是一个合格程序员在基础数论方面应有的素养。下次当你遇到需要求公约数或公倍数的问题时希望你能自信地调用你的“模板”而不是从头开始推导。