蓝桥杯的Java算法题里“求最大公约数”绝对是被翻牌率最高的基础题目之一。它在省赛、国赛里频繁出现有时候是直给有时候披着“数论”“枚举优化”“思维题”的皮最后还是要靠它兜底。我见过不少选手看到这题就心里一松结果又因为各种细节被扣分比如long类型溢出、递归栈爆炸、负数处理甚至死循环。这篇就把蓝桥杯Java里和最大公约数有关的所有坑和正确解法一次说清楚适合正在备赛的同学也适合想系统补一补数论基础的Java开发者。1. 蓝桥杯为什么总拿“最大公约数”开局最大公约数看起来很“小学奥数”但蓝桥杯从来不只考一个公式它靠这题判断你是否具备三件事数学基本功、边界意识、代码稳定性。尤其Java组题目给的数据范围经常是“长整型范围内”这直接卡掉一批只会写int版本的人。1.1 一道看似简单却容易翻车的题先看一个非常经典的题目原型输入描述输入一行包括两个自然数m和nm和n都在长整型范围内。求这两个数的最大公约数。题目短、描述清楚甚至没有复杂的故事背景。但就在这么干净的题面上能翻车的地方非常多。我集训的时候让几个学弟现场做居然有人的第一次提交是int gcd(int a, int b) { while (a ! b) { if (a b) a a - b; else b b - a; } return a; }看着逻辑没错但这方法叫更相减损术在小数字下没问题一旦m和n是长整型范围的极端值比如999999937和999999929这种相邻素数while循环要减上亿次直接超时。更致命的是代码里用的是int参数题目说“长整型范围”一传long直接编译不过。这题目真正想考察的并不是你会不会背辗转相除法而是你能不能认出数据范围、能不能选择对数级别复杂度的算法、能不能写出用long实现的高效版本。1.2 考点拆解数学原理背后的编程思维最大公约数问题背后最核心的数学原理就是两条如果a % b 0那么b就是a和b的最大公约数。对于任意整数a和bb ! 0有gcd(a, b) gcd(b, a % b)这个性质也叫欧几里得引理。这两条合在一起就是辗转相除法的全部逻辑。但蓝桥杯不会只考你递归调用它还会变着法子考你是否会用Math.abs处理负数输入。是否知道a % b在b为0时会抛异常。是否了解long和int在赋值、返回、强转时的精度差异。是否能把最大公约数应用到“最小公倍数”“分数化简”“数组分段”等场景。说白了这题的隐藏考点是“你是否具备从数学定义到代码落地的完整链路”。这也是为什么很多经验帖都把最大公约数当作蓝桥杯Java组的第一道“必做题”。2. 从暴力到优雅三类解法逐个排雷最大公约数的解法在教科书里通常有三种暴力枚举、辗转相除、更相减损。工程上还有一种Stein算法适合超大整数场景。我分别说说它们的实现、坑和适用场景你根据题目要求选型。2.1 暴力枚举法适合小范围热身暴力枚举的思路很直观从min(a, b)开始往1遍历找到第一个能同时整除a和b的数就是最大公约数。代码大概长这样public static long gcdByLoop(long a, long b) { a Math.abs(a); b Math.abs(b); long limit Math.min(a, b); for (long i limit; i 1; i--) { if (a % i 0 b % i 0) { return i; } } return 1; }这个解法在a和b都在1000以内时确实好用逻辑简单不容易写错。但千万别把它带进蓝桥杯正式题。当两个数都是长整型的时候limit可能是几十亿for循环直接跑死。它只能用来热身或者当你在考场上想验证其他算法的正确性时写一个对照组。2.2 辗转相除法蓝桥杯的默认答案辗转相除法也叫欧几里得算法核心就一句话gcd(a, b) gcd(b, a % b)一直递归到余数为0除数就是答案。用Java实现递归版本几乎是一行public static long gcd(long a, long b) { if (b 0) { return Math.abs(a); } return gcd(b, a % b); }迭代版本更稳不会爆栈public static long gcd(long a, long b) { a Math.abs(a); b Math.abs(b); while (b ! 0) { long temp a % b; a b; b temp; } return a; }为什么蓝桥杯偏爱这个算法因为它的时间复杂度是O(log(min(a, b)))即使两个数都接近Long.MAX_VALUE也只需要几十次取模运算就能结束效率极高。而且在标准库设计里Java判断“两个long是否互质”也天然依赖这个算法。注意一个小细节Math.abs(a)在a Long.MIN_VALUE时会返回负数因为绝对值超出了long的正数范围。不过蓝桥杯题目一般给的是自然数如果你自己造数据测到极端负数建议单独处理。比如可以先判断a Long.MIN_VALUE时把它换成Long.MAX_VALUE继续算不过最大公约数定义一般不考虑这种极端边界知道有坑就行。2.3 更相减损术上古定理的古朴写法更相减损术出自《九章算术》原理是两个正整数a和b如果a b那这个数就是它们的最大公约数否则用大数减小数不断重复直到相等。用Java写出来public static long gcdBySubtract(long a, long b) { a Math.abs(a); b Math.abs(b); while (a ! b) { if (a b) { a - b; } else { b - a; } } return a; }这个算法在数论史上的地位很高但在蓝桥杯考试环境里非常容易超时。想象一个极端例子a 1000000000b 1那么要把a减999999999次才能得到1。别笑我真的见过有人用这个方法提交后超时的复盘帖。所以我的建议是更相减损术可以作为概念题了解一下也可以在写“不使用除法、只使用加减法”的特殊题里当备用方案但日常刷题和正式比赛优先考虑辗转相除法。2.4 Stein算法当数字大到想哭的时候如果你去看一些ACM材料会发现还有一个Stein算法。它的思路是只使用移位和加减运算来求最大公约数避免大整数取模的性能消耗。原理基于以下几条如果a和b都是偶数则gcd(a, b) 2 * gcd(a/2, b/2)。如果a是偶数、b是奇数则gcd(a, b) gcd(a/2, b)。如果两个都是奇数则gcd(a, b) gcd((a - b) / 2, b)。Java实现大概是这样public static long gcdStein(long a, long b) { if (a 0) return Math.abs(b); if (b 0) return Math.abs(a); int shift 0; while (((a | b) 1) 0) { a 1; b 1; shift; } while ((a 1) 0) a 1; while (b ! 0) { while ((b 1) 0) b 1; if (a b) { long t a; a b; b t; } b - a; } return a shift; }说实话蓝桥杯Java组里能用辗转相除法轻松解决的问题完全没必要上Stein。Stein算法更适合那些不支持取模运算的嵌入式环境或者处理超长整型比如BigInteger时减少大数除法的开销。如果你只是备赛蓝桥杯把辗转相除法写熟比背Stein有价值得多。了解它的存在即可面试时偶尔能聊两句算个加分项。3. 实战蓝桥杯真题场景与边界处理最大公约数题目本身不难难的是和蓝桥杯的输入输出、数据范围、评测机制打交道。下面这几个实战场景每一个都是我亲眼见过别人丢分的点。3.1 输入输出细节别在Scanner上栽跟头蓝桥杯的输入通常是一行两个数很多人喜欢用Scanner sc new Scanner(System.in); long m sc.nextLong(); long n sc.nextLong();这样没问题但要注意如果题目可能输入多组数据你需要用while (sc.hasNextLong())循环读取。有的同学一上来只读一次写死了单组逻辑遇到测试点把多组数据放在同一个文件里就只通过第一组。另外输出格式尽量用System.out.println(gcd(m, n))。如果你用System.out.print少个换行在个别评测机上会导致多个测试文件的输出黏在一起虽然不一定判错但影响你本地调试时的区分度。别在输出上省事。3.2 长整型范围下的溢出风险题目明确说“m,n都在长整型范围内”这意味着你的返回值也必须是long。如果你写public static int gcd(int a, int b) { ... }然后调用gcd(1234567890123L, 987654321098L)编译器直接报错因为实参已经超出int范围。这属于最基础的编译错误说出去都丢人但每年真的有考生犯。还有一个更隐蔽的溢出问题出现在算最小公倍数时。公式是lcm(a, b) a / gcd(a, b) * b注意顺序先除后乘。如果先乘再除a * b很可能爆long得到负数整个结果全错。我后面会展开讲。在最大公约数本身的计算里递归版本的a % b不会溢出因为取模的结果一定比b小而且b本身是long范围内的合法值。迭代版本更不用担心暂存变量因为temp a % b同样小于b。所以辗转相除法天然是防溢出的这也是它的巨大优势。3.3 最小公倍数与最大公约数的组合拳蓝桥杯经常把最大公约数和最小公倍数放在同一题里比如“求两个数的最大公约数和最小公倍数”。最小公倍数的公式是public static long lcm(long a, long b) { return a / gcd(a, b) * b; }这里必须强调a / gcd(a, b)这一步要先算否则a * b很可能溢出。我第一次带集训时有个同学写的是a * b / gcd(a, b)本地测小数据全对换成Integer.MAX_VALUE和2就输出负数排查半天才意识到是乘法先发生导致溢出。这是最大公约数衍生题里最常见的坑。另一个常见场景是“分数化简”。给定分子分母要求输出最简分数。做法就是用gcd约分long g gcd(abs(numerator), abs(denominator)); System.out.println(numerator / g / denominator / g);这里面还要处理负号一般规范是分母为正如果分母是负数可以把符号移到分子上。别小看这个步骤考题经常会在样例里埋一个-4 / -8的测试点看看你有没有把负号处理好。3.4 多组输入的高频循环性能优化实战有些题目不是只算一组而是给一个数组让你求所有数两两之间的最大公约数之和。这种情况下如果你对每对都调用gcd时间复杂度是O(n^2 log(max))可能够用但如果n是10^5量级就炸了。这时候得用一些预处理技巧。比如先求整个数组的“全局最大公约数”再利用性质“局部最大公约数一定整除全局最大公约数”来做分组。或者用后缀gcd数组做区间查询这个在蓝桥杯的“区间最大公约数”题目里经常出现。示例如下long[] arr new long[n]; long[] suffixGcd new long[n]; suffixGcd[n - 1] arr[n - 1]; for (int i n - 2; i 0; i--) { suffixGcd[i] gcd(arr[i], suffixGcd[i 1]); }这样任意区间[l, r]的最大公约数就能通过线段树或稀疏表进一步优化查询。最大公约数本身虽然是基础题但它往往是复杂算法的一座桥千万别只停留在“会写函数”的层面。4. 常见问题与排查技巧实录我把自己和学员在实际中踩过的坑整理成一张速查表很多问题不看答案自己很难发现。症状原因解法递归版gcd在大数时抛StackOverflowError递归深度偶尔也接近几千默认栈不够改用while循环的迭代版计算最小公倍数得到负数a * b先执行导致溢出改成a / gcd(a, b) * b输入负数时结果不对取模运算对负数行为不符合预期先Math.abs处理多组输入只算第一组没有用hasNextLong循环检查读取逻辑用更相减损术超时算法时间复杂度退化到O(n)换辗转相除法结果总是1返回了int低精度截断全部参数改成long下面挑几个典型问题说说具体的排查思路。4.1 递归栈溢出与迭代改写我见过一个学员用递归写gcd在本地测gcd(1000000007, 1000000009)没事但测gcd(1, 2147483647)就爆栈。其实辗转相除法递归深度一般不会超过几十层但有些极端构造确实能压到几千层Java的默认栈大小通常是1MB可能不够。解决办法很简单一律用迭代也就是while (b ! 0)那个版本既规避栈溢出也更好调试。我个人的习惯是在蓝桥杯代码里永远写迭代版因为递归虽然看着清爽但在线评测环境里多一层栈就多一分不确定风险。4.2 一个“死循环”案例忘记处理负数有次群里有人贴代码求助说自己的gcd一直死循环。原代码大概是这样public static long gcd(long a, long b) { while (a ! b) { if (a b) a - b; else b - a; } return a; }他输入的是-12和18。这个代码在负数下会陷入非常诡异的循环因为a和b相减永远不会收敛。原因很简单更相减损术只适用于正整数它依赖“每次相减后数值变小”的性质负数会让差值越减越大或者一直来回跳。解决方式就是开头统一取绝对值。无论你选哪种算法处理输入后的第一件事永远是a Math.abs(a); b Math.abs(b);这行代码能帮你避开百分之八十的负数坑。4.3 多组输入的循环读取与性能优化有一年模拟赛的题是“连续输入若干行每行两个数输出最大公约数”数据量大概有几十万行。很多同学用sout逐个打印结果测评时间接近超时。Java的System.out.println内部有缓冲区但在高并发输出下性能依然不理想。高频输出我建议用StringBuilder攒着最后统一输出Scanner sc new Scanner(System.in); StringBuilder sb new StringBuilder(); while (sc.hasNextLong()) { long a sc.nextLong(); long b sc.nextLong(); sb.append(gcd(a, b)).append(\n); } System.out.print(sb);这样能显著减少IO次数比赛时可能直接帮你省下一秒多。别小看这一秒蓝桥杯的限时有时候紧得让人想骂人。4.4 蓝桥杯在线评测的“玄学”注意事项蓝桥杯的在线评测系统对Java选手有几个不太友好的点。第一类名必须是Main而不是随便起名。第二不能有package语句否则编译错误。第三提交代码时把注释删干净省得编码问题引起奇怪报错。第四计算时少用Math.pow和Math.sqrt这类浮点函数因为浮点精度在长整型范围下非常不可靠有时会平白丢分。最大公约数问题虽然不涉及浮点但由它扩展的题目比如“判断两个数是否互质”“输出最简分数”如果中间不小心引入了浮点后果就是答案错误。我一般坚持全链路都用整数运算能不用浮点绝不用。5. 从最大公约数延伸出去的必考知识点最大公约数不是孤立的它在蓝桥杯里往往只是一个跳板后面还牵扯着一串其他题型。做题时把它和周边知识打通你会发现很多所谓“难题”不过是套了层壳。5.1 多个数的最大公约数求三个或更多正整数的最大公约数本质是不断两两求公约数。代码很简单但很多人会问“多个数能不能一次算出平均值”答案是直接套性质public static long gcdArray(long[] arr) { long result 0; for (long val : arr) { result gcd(result, val); if (result 1) { break; } } return result; }注意这里初始result设为0因为gcd(0, x) x。一旦中途遇到1整个数组的最大公约数一定是1可以直接跳出节省时间。蓝桥杯有一类“数组分段”题就会用到这个性质来做提前剪枝。5.2 最大公约数的数论应用线性丢番图方程还有一个进阶方向是扩展欧几里得算法能求ax by gcd(a, b)的一组整数解。蓝桥杯Java组偶尔会考到题干可能表述为“求某个模线性方程的解”。比如public static long[] exgcd(long a, long b) { if (b 0) { return new long[]{a, 1, 0}; } long[] res exgcd(b, a % b); long gcd res[0]; long x1 res[1]; long y1 res[2]; return new long[]{gcd, y1, x1 - a / b * y1}; }乍一看有点绕但其实它就是在辗转相除过程中保留每一步的系数。很多选手看到“扩展欧几里得”就吓跑了但实际上只需要半小时就能掌握。建议备赛时间充裕的话把exgcd也写了因为它能直接解决“中国剩余定理”里最关键的一步而“中国剩余定理”在蓝桥杯国赛的Java组里也算高频考点了。5.3 最大公约数在热门算法题里的“伪装”热词里出现了“给定一个由2n个正整数组成的数组先舍弃其中两个元素将其余元素两两配对使每对元素的和构成新数组构造一种配对方式使新数组所有元素的最大公约数大于1”这其实就是一道穿着“构造题”外衣的最大公约数思维题。这种题你会不会做完全取决于你熟不熟悉最大公约数的性质。基本思路是去找一个公共因子比如2把所有数按奇偶性分类通过舍弃两个数让配对的和变成偶数。你看到最后还是在考“偶数偶数偶数”“奇数奇数偶数”这种基础中的基础但如果没有GCD的思维训练很容易一道题卡到结束。所以别以为求最大公约数只是练手很多省赛压轴题的突破口就是你能不能快速联想到“两数之和的公约数”这个角度。6. 几个能让你比赛更稳的实操习惯最后聊点题外话都是我带队几年积攒下来的经验。最大公约数题目虽然简单但比赛时的稳定性往往藏在细节里。先把模板背进肌肉记忆。我建议每个人都在本地建一个“数论模板”文件里面放好public static long gcd(long a, long b) { a Math.abs(a); b Math.abs(b); while (b ! 0) { long tmp a % b; a b; b tmp; } return a; }这个函数从头到尾没有一行多余的判断没有递归没有潜在的栈风险是我用了五年以上的标准写法。平时刷题时凡是涉及约分、整除、互质一律先调它。等上了考场看到“最大公约数”五个字你的手会自动打出这段代码根本不需要大脑思考。再准备一个测试用的极端样例集合gcd(0, 5) 5gcd(Long.MAX_VALUE, Long.MAX_VALUE - 1) 1gcd(12, 18) 6gcd(-4, 8) 4gcd(1000000007L, 1000000009L) 1这些用例能在一分钟内验证你的实现是不是真的稳。我见过有人自信满满地提交结果连gcd(0, 5)都没过因为返回了0。这种低级错误在紧张的环境下特别容易犯。另外顺手写一个最小公倍数函数public static long lcm(long a, long b) { return a / gcd(a, b) * b; }蓝桥杯很多题要求输出最大公约数和最小公倍数一次写对两个省得现场临时拼。最后想说的是最大公约数是整个算法竞赛里“性价比”最高的知识点之一。它代码量少却能引出扩展欧几里得、中国剩余定理、莫比乌斯反演等一系列大块头。把这一道基础题吃透你不仅能拿稳送分题也能在遇到隐藏考察点的时候比别人先缓过劲来。备赛时别嫌题简单多花点时间研究它的变体和边界比赛时你会感谢现在的自己。
