最大公因数和最小公倍数这两个概念从小学算术一路陪到算法笔试但真正能把它们讲透、用对、写稳的人并不多。BISHI57这个编号看起来像某套笔试题库里的第57题也可能是某个课程项目的编号不管哪种核心考察点都是一致的你懂不懂欧几里得算法的本质能不能写出兼顾正确性、效率和边界处理的代码。这篇文章我把最大公因数GCD和最小公倍数LCM从数学原理到代码实现、从单个数对到批量场景、从常见陷阱到性能分析全部过一遍适合正在准备笔试面试的同学也适合刚学算法想把手底基本功打牢的初学者。1. 内容整体设计与思路拆解1.1 为什么GCD和LCM值得单独写一篇先说个实际现象。我在各种笔试平台和课程作业里见过太多这样的代码循环从1遍历到min(a,b)一个个试能不能同时整除。功能没错结果也对但数据一上来就原形毕露。a和b如果是10的9次方量级枚举法少说几亿次循环几秒钟就这么耗没了。而辗转相除法欧几里得算法只要几十次取模运算就能出结果差距是数量级的。所以GCD和LCM看起来是小学数学实际上是检验一个程序员对算法复杂度有没有概念的好题目。它不涉及复杂的数据结构不需要高深的动态规划纯粹看你愿不愿意多想一想数学上的等价关系能不能把枚举优化成递推。这也解释了为什么笔试和课程作业都爱出这道题代码量不大但坑特别多负数、零、溢出、递归边界任何一个没处理好都可能挂。想拿全分光会背模板不行得真正理解每一行代码为什么这么写。1.2 完整的知识地图这篇博文的展开逻辑是这样的先搞清楚GCD和LCM的数学定义以及它们之间的换算关系这是后面所有实现的理论根基。然后比较几种求解算法枚举法、更相减损术、辗转相除法分析它们各自的原理和复杂度。接着是实际的代码实现覆盖Python、C、Java三个常用语言给出递归和迭代两种版本同时展示标准库的调用方式。再往前走一步处理多个数的GCD/LCM、大数据场景下的溢出防护、实战中容易出错的地方。最后整理一份问题排查速查表把我在实际开发和判题过程中遇到的典型问题列出来。整个思路是数学原理 → 算法设计 → 代码落地 → 边界处理 → 经验总结这样走一遍遇到的题目基本都不会再卡壳。2. 数学基础与核心公式推导2.1 定义不能含糊最大公因数也叫最大公约数指两个或多个整数共有约数中最大的一个。比如12和18约数分别是1、2、3、4、6、12和1、2、3、6、9、18公共约数是1、2、3、6最大的是6所以gcd(12, 18) 6。最小公倍数指两个或多个整数公有的倍数中最小的一个。12的倍数有12、24、36、48、60、72……18的倍数有18、36、54、72……公共倍数是36、72……最小的是36所以lcm(12, 18) 36。这里有个容易混淆的点有些教材和工具里把最大公因数写成Greatest Common Divisor缩写GCD也有的写成Greatest Common FactorGCF或者Highest Common FactorHCF指的都是同一个东西。最小公倍数则是Least Common Multiple缩写LCM。英文缩写反而比中文更统一因为中文里公因数和公约数两种叫法都存在。2.2 关键公式LCM和GCD的桥梁最大公因数和最小公倍数之间有一个非常重要的关系lcm(a, b) |a × b| / gcd(a, b)这个公式是几乎所有LCM题目的核心推导思路也很直观。设a gcd(a,b) × pb gcd(a,b) × q其中p和q互质。那么a和b的公倍数可以写成gcd(a,b) × p × q × kk是任意正整数当k1时取得最小值也就是gcd(a,b) × p × q |a × b| / gcd(a,b)。加绝对值是因为负数参与运算时倍数关系里的负号没有实际意义我们通常取正的最小公倍数。有了这个公式求解LCM就不需要单独设计算法先算GCD再套公式即可。但这里埋了一个坑a × b可能会溢出。比如a和b都在10的9次方量级乘积就是10的18次方在32位int里直接存不下。所以工程上更稳妥的写法是先除后乘lcm(a, b) a / gcd(a, b) × b前面这个写法在C里用int会炸Python和Java因为整数范围不同情况也不一样这一点后面实操章节我会专门展开讲。2.3 三种求解算法对比枚举法从min(|a|, |b|)向下遍历找到第一个能同时整除a和b的数就是GCD。这个办法优点是零思考量缺点是时间复杂度O(min(a,b))数据一大完全不可用笔试的时候如果没做复杂度分析就交上去大概率超时。更相减损术出自《九章算术》核心是gcd(a, b) gcd(a-b, b)假设a b。不断用较大的数减去较小的数直到两个数相等这个相等的数就是GCD。这个算法优点是只用减法和比较不需要取模运算在某些对除法有性能瓶颈的平台上可能占优。缺点是当两个数相差悬殊时操作次数很多比如gcd(1, 1000000000)要循环9亿多次。辗转相除法欧几里得算法核心是gcd(a, b) gcd(b, a mod b)一直递归到余数为0最后的非零除数就是GCD。这个算法时间复杂度是O(log(min(a, b)))是当前最主流的方案也是笔试里最推荐写的。它们的关系可以这样理解更相减损术是多次减法辗转相除法本质上是用一次取模代替多次减法效率自然高得多。3. 核心细节解析与实操要点3.1 递归写法要注意的细节先从最经典的递归写法说起拿Python举例def gcd(a: int, b: int) - int: if b 0: return a return gcd(b, a % b)这个写法非常简洁但新手最容易问的问题有两个为什么终止条件是b 0而不是a 0或者a b递归里取模会不会栈溢出第一个问题我想用一个递推链来说明。假设要算gcd(48, 18)。按照渐进式推演gcd(48, 18)48 % 18 12问题变成gcd(18, 12)gcd(18, 12)18 % 12 6问题变成gcd(12, 6)gcd(12, 6)12 % 6 0问题变成gcd(6, 0)此时b 0直接返回a 6你会发现当b变成0时说明上一轮取模已经整除干净了a就是最后那个非零余数也是最终的GCD。所以终止条件必须是判断b是否为0。第二个问题递归深度严格来说是O(log(min(a,b)))在正常数据范围内不会超过几十层Python默认递归限制是一千层完全够用。真正需要警惕的不是深度而是取模运算本身的正确性——如果b为负数a % b的结果在不同语言里可能行为不同这个后面排查章节单独说。3.2 迭代写法的优势与实现递归写法逻辑清晰但有些场合我更推荐迭代版本原因有三一是规避了递归调用的函数栈开销二是看起来更接近工程实践三是写C/C的时候不会因为编译器优化的差异产生不确定性。def gcd_iter(a: int, b: int) - int: while b ! 0: a, b b, a % b return aPython里的元组赋值一次性完成交换和取模这个写法业内称为辗转相除的单行循环版。C版本的迭代写法类似int gcd(int a, int b) { while (b ! 0) { int t b; b a % b; a t; } return a; }只要理解了把旧的b作为新的a把余数作为新的b这个循环不变量迭代版本和递归版本在逻辑上是完全等价的。3.3 标准库与手写代码的选择实际工程开发中不需要自己造轮子。Python从3.5开始可以直接用math.gcdC17标准库里有std::gcdJava有BigInteger.gcd方法。这些标准库实现久经考验性能不会比你手写的差优先用于生产代码。但笔试和面试场景建议还是自己手写一遍。原因很直接有些笔试环境不允许导入某些库或者判题机上的标准版本和你本地有差异。更重要的是面试官想看到的是你对原理的理解你一行import就完事了根本看不出你的水平。手写递归版本通常三五行就搞定性价比极高。稳妥策略是两种都会工程代码用标准库笔试手写核心逻辑。3.4 多数的GCD和LCM处理遇到三个或更多数的GCD/LCM要注意计算的结合性gcd(a, b, c) gcd(gcd(a, b), c) lcm(a, b, c) lcm(lcm(a, b), c)这个结论从质因数分解的角度最容易理解。每个数的质因数分解结果取公共部分的最小指数就是GCD取各数中最大指数的乘积就是LCM。多个数时逐对累积即可。代码实现上可以用reducefrom functools import reduce from math import gcd def gcd_many(nums: list) - int: return reduce(gcd, nums) def lcm_many(nums: list) - int: l 1 for n in nums: l l // gcd(l, n) * n return l这里lcm_many也用了先除后乘的方式防溢出。4. 实操过程与核心环节实现4.1 完整实现Python版本我把一套完整的、带输入校验的Python实现贴在下面这套代码可以直接跑判题import sys from math import gcd def lcm(a: int, b: int) - int: if a 0 or b 0: return 0 return a // gcd(a, b) * b def main(): data sys.stdin.read().strip().split() if not data: return nums list(map(int, data)) # 题目要求通常是每行两个数这里支持一次输入多个数 for i in range(0, len(nums), 2): a, b nums[i], nums[i1] print(gcd(a, b), lcm(a, b)) if __name__ __main__: main()这个实现的几个设计点分别是用sys.stdin.read一次性读取避免逐行读取在数据量大时拖慢速度手动处理空输入lcm用了先除后乘防止a×b溢出。这些都是笔试实战里很有用的小细节。4.2 完整实现C版本C写这道题要特别注意数据类型因为int范围在很多判题平台上是32位超过2的31次方减1就会溢出#include iostream #include numeric // std::gcd using namespace std; long long gcdll(long long a, long long b) { while (b ! 0) { long long t b; b a % b; a t; } return a; } int main() { long long a, b; while (cin a b) { long long g gcdll(a, b); long long l a / g * b; cout g l endl; } return 0; }我习惯用long long而不是int这是一个性价比极高的习惯。两个int量级的数相乘就可能超出int上限用long long可以覆盖大多数题目的数据范围。如果题目给到10的18次方这种极端范围那long long也不够得换Java的BigInteger或者Python这种任意精度语言。4.3 完整实现Java版本Java没有内置的int类型GCD函数但BigInteger提供了现成方法。如果是普通笔试直接手写一个静态方法就行import java.util.Scanner; public class Main { static long gcd(long a, long b) { while (b ! 0) { long t b; b a % b; a t; } return a; } public static void main(String[] args) { Scanner sc new Scanner(System.in); while (sc.hasNextLong()) { long a sc.nextLong(); long b sc.nextLong(); long g gcd(a, b); long l a / g * b; System.out.println(g l); } sc.close(); } }Java的取模运算对负数的行为和数学定义更接近结果是负余数但在我们讨论的非负数域里上面的写法就足够稳。假如题目明确说输入可能是负数需要先对输入取绝对值再进入算法流程。4.4 性能分析与数据测试为了让大家直观感受几种算法复杂度差异我做了一组简单测试。以Python 3.11、计算gcd(2147483647, 2147483646)为例枚举法从2147483646开始向下逐个数试除最坏情况要遍历约21亿次测试中运行时间超过60秒直接放弃等结果。更相减损术这两个数相差1减完一轮就变成gcd(2147483646, 1)接下来要减21亿次同样不可接受。辗转相除法第一次取模就得到gcd(2147483646, 1)然后gcd(1, 0)两步完成耗时微秒级。这个测试告诉我们笔试里一旦出现大数GCD只要不是辗转相除/欧几里得体系基本等于超时没商量。另一组常规数据测试数据都是构造出来的常见样例输入gcdlcm说明(12, 18)636最基础案例(0, 5)500参与的边界(7, 13)191互质情况(1071, 462)2123562欧几里得原文案例(100, 100)100100相等情况互质情况的LCM等于两数乘积很多人在这一点上容易粗心总觉得最小公倍数应该比两个数都大其实两个数相等时LCM就等于它们本身互质时LCM等于乘积这些边界都需要考虑。5. 常见问题与排查技巧实录5.1 负数参与的GCD与LCM理论上GCD应该为正数但笔试输入偶尔会出现负数。我们用辗转相除法时取模在负数下的行为各语言不一致。举一个具体例子Python(-12) % 18 6所以gcd(-12, 18) gcd(18, 6) 6结果正数凑巧没关系C-12 % 18 -12gcd(-12, 18)会进入gcd(18, -12)再算18 % (-12) 6最后也得到6但中间符号处理混乱靠运气对Java同C-12 % 18 -12这种不确定性让排查变得困难。最稳妥的方案是在入口处统一处理def gcd_safe(a: int, b: int) - int: return gcd(abs(a), abs(b))LCM涉及符号时也类似通常约定返回正的最小公倍数用abs处理输入即可。5.2 整数溢出最隐蔽的杀手老生常谈但必须再谈一次。lcm(a, b) a * b // gcd(a, b)这个写法在Python里没问题因为Python的整数是任意精度在C和Java里就是隐患。举例a 2000000000b 2000000000gcd 2000000000lcm应该还是2000000000。但如果先算a * b 4 × 10^18这个值已经超过32位int能表示的最大值约2.1 × 10^9直接溢出成负数结果自然错得离谱。即使换成long long如果a和b都到10^9级别乘积10^18也接近long long上限再往上就危险。正解就是那四个字先除后乘。先做a // gcd(a, b)把数值先降下来再乘b。这个顺序能保证中间结果尽量小是经验性常识也是我在很多代码评审里反复强调的点。5.3 输入处理不当导致的非预期行为笔试判题的数据格式五花八门。有的是每行两个数有的是一行所有数有的带空格有的带逗号。我在实际做题和帮学生改代码时见过不少因为输入格式而挂掉的案例。建议的方案是不依赖具体的换行结构把整个输入读进来按空白字符切分转成int列表然后每两个一组处理。这样不管是换行分隔还是空格分隔都能兼容。如果题目明确保证输入合法就不需要再做复杂校验如果不确定至少加一个if not data: return的空输入保护。5.4 递归深度与重复计算虽然辗转相除的递归深度很小但有一种场景会真的爆栈在循环里反复调用递归版gcd且递归实现写得不好。比如某些语言默认栈空间很小如果递归层数达到几千就可能StackOverflow。遇到这种环境直接改用迭代版。另外多个数连续求LCM时不要每轮都从头开始算GCD。比如res nums[0] for i in range(1, len(nums)): res res // gcd(res, nums[i]) * nums[i]这个写法每次只算当前结果和下一个数的gcd不会重复计算性能比较好。如果写成先算所有数的gcd再统一处理逻辑上等价但中间变量可能偏大。5.5 易错点速查表易错点错误写法正确做法枚举法求GCD从1向上遍历记录最大辗转相除法O(log n)LCM溢出lcm a * b // gcd(a,b)lcm a // gcd(a,b) * b负数输入直接参与取模先abs再计算0参与LCM返回a*b任何数与0的LCM定义为0递归爆栈深度大时仍用递归改用迭代版多组输入只处理一行循环读取至EOF5.6 从笔试到工程GCD与LCM的延展价值把这道题吃透收益远不止笔试多拿几分。GCD和LCM在很多实际问题里都有出场机会分数化简是GCD最常见的应用。分子分母同时除以gcd后就是最简分数日常做报表、做单位换算都会用到。周期同步问题可以用LCM建模。两盏灯分别每6秒和8秒闪一次同时闪的间隔就是lcm(6, 8) 24秒。RSA加密算法的密钥生成依赖大数的GCD计算欧几里得算法在那里被用来求模逆元是数论应用的重要环节。竞赛题里的同余方程组也大量使用GCD相关理论。会了这道基础题后面的扩展内容再上手就顺畅多了。6. 小技巧与扩展思考最后再分享两个实战里摸索出来的小技巧。第一个是用二进制算法Stein算法代替模运算对超大整数的GCD求解在某些场景下比欧几里得算法更快。Stein算法的核心是利用右移操作替代取模避免了大数除法昂贵的开销。Python的math.gcd在Python 3.9的CPython实现中就会根据数据大小选择更快路径这也是为什么我建议实际工程直接用标准库的原因之一。第二个技巧是当你需要频繁计算大量数对的GCD/LCM时可以考虑预处理或缓存的思路。比如分数化简的批量操作中先提取所有分子分母的公共因子再用哈希缓存已经算过的数对可以省掉大量重复计算。笔试里可能用不上但是实际工程里数据量上来之后这个收益是看得见的。回到BISHI57这道题本身它考察的东西其实很朴素一个两千多年前的算法一个简单到不能再简单的公式再加上对边界条件的敬畏之心。把这三样吃透了以后不管题目怎么变形万变不离其宗。我自己的体会有两点一是永远不要在能用O(log n)解决的问题上写O(n)的代码二是永远不要把乘法放在除法前面。这两条原则愿与看到这里的各位共勉。