1. 问题还原与题目解读 —— 先搞清楚题目到底在问什么说起蓝桥杯2013年第四届的真题“核桃的数量”不少刷过题库的同学第一时间都会冒出两个字简单。但就是这么一道“简单题”每年都有第一次参赛的人因为读题不仔细、求错了东西、或者根本没理解“最小”这两个字的含义而丢分。这道题放在当年属于基础送分题但它背后隐藏的数学原理和代码实现细节其实值得掰开揉碎讲清楚。1.1 原题描述与核心条件拆解原题的场景是这样的小张是软件项目经理带领3个开发组工期紧今天都在加班。为了鼓舞士气小张打算给每个组发一袋核桃。他的要求有三条各组的核桃数量必须相同各组内必须能平分核桃即每组的人数要能整除该组拿到的核桃数在满足前两条的前提下尽量提供满足条件的最小数量。输入是三个正整数分别表示三个组的人数输出一个整数表示每袋核桃的数量。比如样例输入是“2 4 5”输出是“20”。这个条件看起来很简单但很多人第一次做的时候会下意识地算出三个数的最大公约数或者干脆三个数相乘直接输出。这些做法都不对。仔细读题“各组内必须能平分核桃”意味着每组拿到的核桃数量 N 必须能被该组人数整除也就是 N 是每组人数的倍数。而“各组的核桃数量必须相同”意味着我们要找同一个 N让它同时是三个组人数的倍数。再加上“最小数量”这个问题的本质就浮出水面了求三个正整数的最小公倍数英文缩写 LCMLeast Common Multiple。1.2 为什么这道题经典且值得反复练习在蓝桥杯的早期真题里很多题目都习惯性地把算法包装在一个生活场景当中。核桃的数量就是非常典型的一道“数学建模”题它考察的并不是多高深的算法而是你能不能从一段生活化的描述里准确抽取出数学关系。这种能力恰恰是竞赛中最重要、也最容易被忽视的基础素养。说白了这道题就是“应用题”考的是两件事第一读题后能不能提取出“同时整除”和“最小”这两个核心关键词第二会不会用辗转相除法求最大公约数进而推出最小公倍数。第二个能力是实打实的编码基本功。很多同学在学校里学过辗转相除法但一到考场就只记得“两个数的最大公约数”遇到三个数就懵了。这道题把“两个数”的场景扩展到了“三个数”难度没怎么增加但思路必须跟着调整于是就成了一个非常好的训练样本。2. 从数学原理到算法模型 —— 本质是最小公倍数问题核桃这一题在数学上没有任何弯弯绕绕但它能很好地检验你对“整除、倍数、公约数、公倍数”这一组基础概念的掌握程度。我见过不少非科班出身、半路转行学编程的同学一看到“最小公倍数”这个词就发怵觉得是小学数学的阴影。其实如果你真搞懂了公倍数的定义代码写起来比四则运算复杂不了多少。2.1 题目如何转化为数学问题先做个简单的符号约定。设三个组的人数分别为 a、b、c设每袋核桃数量为 n。题目要求n 能被 a 整除即 a 是 n 的因子n 能被 b 整除n 能被 c 整除n 是所有满足上述条件的正整数里最小的那一个。翻译成数学语言就是求满足以下同余条件的最小正整数 nn % a 0 n % b 0 n % c 0满足这三个条件的数有无限多个比如 a × b × c 一定可以2 × a × b × c 也可以但题目要的是“最小”的那个。最小公倍数的定义恰好就是这个几个数共有的倍数中最小的那个。这里有个非常容易混淆的点最大公约数GCD看起来和最小公倍数长得很像名字里都有“公”字但实际上解决的问题完全不同。最大公约数解决的是“把东西平均分给几组最多能分成多少份”的问题比如把若干苹果分给若干小朋友每个小朋友分到的一样多问每人最多能拿几个这就是最大公约数的典型场景。而最小公倍数解决的是“几件事同时周期性发生什么时候再次同时发生”的问题比如 A 车每 6 分钟发一班B 车每 8 分钟发一班两车同时发车后多少分钟后又同时发车这就要找最小公倍数。核桃这题说“每组人数各自能整除核桃数”本质上是找“同时是三个人数的倍数”的数所以必须用最小公倍数。2.2 最小公倍数与最大公约数的关系两个数 a 和 b 的最小公倍数有一个非常重要的公式lcm(a, b) a * b / gcd(a, b)这个公式必须记牢因为它把求最小公倍数的问题转化成了求最大公约数的问题。而最大公约数有一个非常经典的算法辗转相除法也叫欧几里得算法。这个算法的核心思想是两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。用公式表达就是gcd(a, b) gcd(b, a % b)直到余数为 0 时当前的非零除数就是最大公约数。为什么这个公式成立可以用一个简单的例子感受一下。设 a 12b 812 % 8 4那么 gcd(12, 8) gcd(8, 4)8 % 4 0所以 gcd(12, 8) 4。这个过程本质上是把两个数不断缩小直到一个数能整除另一个数为止。理解了原理之后再回头看 lcm 的公式。为什么 a × b 之后再除以 gcd 就得到最小公倍数因为 a × b 一定是 a 和 b 的公倍数但可能不是最小的它多乘了一个“公共因子”。把这个公共因子除掉剩下的就是最小的那个公倍数。这样说可能还是有点抽象换个角度把 a 和 b 拆成质因数的乘积最小公倍数就是把所有出现过的质因数按最高次数乘起来而 a × b / gcd 恰好等价于这个操作。2.3 三个数的LCM怎么求很多第一次做这道题的人会卡在一个地方公式 lcm(a, b) a * b / gcd(a, b) 只适用于两个数三个数怎么办答案是分两步走。先求出前两个数的最小公倍数再拿这个结果和第三个数求最小公倍数lcm(a, b, c) lcm(lcm(a, b), c)为什么这样可行因为最小公倍数本质上是一个满足“能被 a、b、c 同时整除”的数先求 lcm(a, b) 得到一个数 t这个 t 能被 a 和 b 同时整除。再求 lcm(t, c)得到的新数既能被 t 整除也就能被 a 和 b 整除同时又能被 c 整除所以它一定是 a、b、c 的公倍数。而数学上可以证明这样得到的结果恰好是最小的那一个。这个“两两合并”的思路非常通用。以后不管求几个数的最小公倍数哪怕给你十个八个数也都用同一个套路拿一个结果往下一个数上合并。说白了就是滚动更新一次只处理两个对象。3. 代码实现与细节解析 —— 三种语言的完整解法核桃的数量这道题对代码本身的要求不高一般学会循环或者递归就能写出来。但不同语言在实现上还是有一些细节差异的尤其是在“求最大公约数”的过程中整数溢出的问题需要特别注意。下面我分别给出 C/C、Python 和 Java 的实现每段代码都会逐行讲清楚。3.1 C/C 实现与讲解C/C 是蓝桥杯最主流的参赛语言之一代码风格偏向简洁高效。先说最关键的一点求 gcd 时用递归还是迭代递归写法更贴近数学定义代码量少但对新手来说容易在边界条件上出错迭代写法稍微多几行但逻辑更直观不容易写错。我建议初学者先用迭代写等熟练了再考虑递归。#include iostream using namespace std; // 辗转相除法求最大公约数迭代实现 int gcd(int a, int b) { while (b ! 0) { int temp a % b; a b; b temp; } return a; } // 求最小公倍数 int lcm(int a, int b) { return a / gcd(a, b) * b; } int main() { int a, b, c; cin a b c; int ans lcm(lcm(a, b), c); cout ans endl; return 0; }注意一个细节在 lcm 函数里我写的是a / gcd(a, b) * b而不是a * b / gcd(a, b)。这两者在数学上完全等价但在计算机上有巨大差别。如果 a 和 b 都是比较大的整数比如 a 100000b 99999那么 a × b 可能会超出 int 的表示范围造成溢出而先做除法再乘法就能有效避免中间结果过大。这道题的数据范围比较小一般不会溢出但养成“先除后乘”的习惯在以后的竞赛中能帮你避开很多坑。再解释一下主函数里的写法lcm(lcm(a, b), c)就是把前两个数的结果和第三个数继续合并这正好对应前面说的“两两合并”思路。如果不习惯嵌套调用也可以拆开写int t lcm(a, b); int ans lcm(t, c);3.2 Python 实现与讲解Python 自带 math 库里面有现成的math.gcd函数所以在蓝桥杯的 Python 组里这道题可以写得非常短。但这里我强烈建议即使有现成函数也一定要自己手写一遍 gcd。原因很简单竞赛环境里你可能会忘掉库函数的名字或者遇到不允许用某些库的环境手写能力才是真正属于你自己的。def gcd(x, y): while y: x, y y, x % y return x def lcm(x, y): return x // gcd(x, y) * y a, b, c map(int, input().split()) print(lcm(lcm(a, b), c))Python 的整数没有溢出问题所以x // gcd(x, y) * y和x * y // gcd(x, y)结果都一样但我还是习惯先除后乘这样可以在思维上保持一致性避免换一种语言时忘了这一点。如果你非要用现成的 math 库可以这样写from math import gcd def lcm(x, y): return x // gcd(x, y) * y a, b, c map(int, input().split()) print(lcm(lcm(a, b), c))这两段代码都能通过。但说句实在话刷题阶段用库函数节省下来的时间远不如自己动手实现一遍学到的东西多。我当年刷这道题的时候就是先自己实现再去对比库函数版本发现原来库函数内部也是用辗转相除法那种“原来如此”的感觉让人印象很深。3.3 Java 实现与讲解Java 在蓝桥杯里也算常见语言。Java 的BigInteger类里提供了gcd方法但常规整数运算下没必要用它直接手写即可。import java.util.Scanner; public class Main { static int gcd(int a, int b) { while (b ! 0) { int temp a % b; a b; b temp; } return a; } static int lcm(int a, int b) { return a / gcd(a, b) * b; } public static void main(String[] args) { Scanner sc new Scanner(System.in); int a sc.nextInt(); int b sc.nextInt(); int c sc.nextInt(); System.out.println(lcm(lcm(a, b), c)); sc.close(); } }Java 的静态方法组织方式让代码结构显得更清晰主函数负责读入和输出gcd 和 lcm 各自负责一块逻辑。这里我特别想提一下Scanner的关闭问题。很多同学平时写练习代码时不关 Scanner感觉无所谓但在实际项目或严格的代码规范里资源不释放是一种不好的习惯。竞赛题虽然不会因为这个扣分但好的习惯要从一开始就养起来。4. 易错点分析与测试用例设计蓝桥杯前几届的题目通常数据范围都很温和核桃的数量也不例外。但这道题的“坑”不在于数据强度而在于思维盲区。我见过太多人在这道题上栽跟头总结下来主要有三类错误求成了最大公约数、直接把三个数相乘、以及在求 LCM 时写错公式导致死循环或除零错误。4.1 边界情况与特殊输入先看输入范围。三个正整数最小都是 1。如果输入是“1 1 1”那每袋核桃数量就是 1因为 1 能同时被三个组的 1 个人平分而且它是最小的正整数。这个用例看似无聊却是检验代码是否处理了最小边界的有效手段。如果代码里求 gcd 时误把某个变量写成 0这种用例会直接触发除零错误。再看另一种情况“1 2 3”。最小公倍数是 6因为 6 能同时被 1、2、3 整除而且没有任何比 6 更小的正整数满足这个条件。这个用例能很好地检验你的“两两合并”思路是否正确lcm(1, 2) 2lcm(2, 3) 6没问题。还有一个值得注意的情况是三个数互质比如“2 3 5”。最小公倍数是 30恰好等于三数相乘。很多人看到“恰好等于乘积”就以为自己写对了但其实这只是一个特例。真正检验代码正确性的用例是“2 4 5”也就是题目给出的样例最小公倍数是 20而不是 2 × 4 × 5 40。如果一个数能被另一个数整除比如“3 6 9”最小公倍数是 18而不是 162。如果你用“先乘后除”的公式且没有约分就会得到 162这显然是错的。我的建议是在提交之前至少跑以下几组测试输入 (a, b, c)预期输出说明1 1 11最小边界1 2 36含 1 的混合情况2 4 520官方样例3 6 918倍数关系2 3 530两两互质7 11 131001大互质数检验溢出处理4.2 常见错误模式错误一把“最小公倍数”当成“最大公约数”。这可能是最可惜的一种错误因为如果题目问的是“把核桃平均分成若干份问每份最多几个”那确实要用最大公约数。但这里的场景是“每组内要能平分”对象反了思路也跟着反了。我遇到过一位同学他代码写得非常工整辗转相除法也写对了但最后输出的是 gcd(a, b, c)样例“2 4 5”输出 1直接错得离谱。错误二直接输出 a * b * c。这种写法在“2 3 5”这种互质样例上能蒙对但换一个“2 4 5”就变成 40 而不是 20。竞赛题目不会白给你样例输入样例之所以选“2 4 5”就是因为 2、4、5 两两之间不全是互质能有效区分“直接相乘”和“正确求 LCM”的做法。错误三求 LCM 时先相乘导致溢出。前面已经说过C/C 的 int 在部分编译器下只有 32 位能表示的最大值约 21 亿。如果三个数都接近 10 万乘积就会到达 10 的 15 次方量级直接溢出。虽然这道题的数据范围未必这么大但这是一个非常不好的习惯。在以后的竞赛题里数据范围动辄 10 的 9 次方一旦先乘后除很容易踩雷。错误四递归求 gcd 时忘记终止条件。比如写成gcd(a, b) gcd(b, a % b)但没写if (b 0) return a;运行时就会无限递归最终栈溢出。这个错误在新手中出现的频率比想象中高因为数学公式看起来“自动会停”但计算机不会。4.3 测试用例设计思路做题不要只看样例过了就提交这是新手最容易犯的毛病。设计测试用例时要刻意覆盖三类情况边界1、倍数关系3 6 9、互质关系2 3 5。边界用例能检验代码的健壮性倍数关系能检验你是否真的理解了 LCM互质关系能检验公式是否写对。把这三类都跑一遍这道题基本就稳了。5. 从这道题延伸出去的算法思维一道“送分题”的价值远不止 AC 本身。如果只是把代码抄一遍、提交通过、然后丢掉那刷题的效果会大打折扣。核桃的数量虽然简单但它牵涉的数学抽象能力和代码实现能力在很多后续题目里都会用到。5.1 竞赛题目如何从生活场景抽象成数学模型我经常跟身边的朋友说竞赛题本质上是在考察“把自然语言翻译成数学语言”的能力。核桃的题目是一道非常典型的生活场景题它用“发核桃”这个动作掩盖了“最小公倍数”这个数学概念。如果你能一眼看穿这层包装说明你的抽象能力已经过关。这种抽象能力是可以刻意训练的。拿到任何一道题先不要急着一行一行读而是先问自己三个问题输入是什么输出是什么约束条件是什么把这三个问题回答清楚题目已经被你拆掉一半了。核桃这题的输入是三个人数输出是一个正整数约束条件是“同时整除且最小”答案自然浮出水面。5.2 这类题目的举一反三从核桃的数量出发可以延伸出好几个变体。最常见的变体是“求多个数的最小公倍数”给五个数、六个数甚至更多思路完全一样两两合并就行。还有一个变体是“分数通分”本质上也是求分母的最小公倍数。另一个方向是把 LCM 和 GCD 结合起来考比如“已知两个数的 GCD 和 LCM反求这两个数”这类题在数论题里也经常出现。更远一点的延伸是“周期问题”。比如三盏灯分别每隔 a 秒、b 秒、c 秒闪一次问多少秒后三盏灯同时闪这就是最小公倍数的实际应用。理解了核桃这道题你就等于掌握了处理这类周期同步问题的核心工具。5.3 我在这道题上的一些实际体会说句实话我最初做这道题的时候也犯过错。当时年少轻狂一看题目觉得简单直接三个数相乘提交上去样例过了心里还挺美。结果交到评测系统里WA 得明明白白。从那以后我养成一个习惯不论题目多简单都要先想清楚“数学上它到底在问什么”再动手写代码。后来我在给其他人讲这道题时发现一个问题非常普遍很多人在理解“各组内必须能平分核桃”这句话时会把“组内人数”和“组数”搞混。题目说的是每组的人数不是组数。三个组的人数分别是 a、b、c每组拿到一袋数量为 n 的核桃要求 n 能被 a、b、c 各自整除。如果你把“组内人数”理解成“组数”整道题就完全偏了。还有一个细节值得单独提一下题面里说“每袋核桃的数量”也就是说三袋核桃数量相同而不是三个组分到的总数相同。这个细节和第一条要求“各组的核桃数量必须相同”是呼应的。有了这句话问题被严格限定成了“求同一个数 n”不存在什么“第一组拿 6 个、第二组拿 12 个”这种分配方案。6. 实战演练与对比分析 —— 从暴力枚举到数学解法聊完原理和常见错误我想再补充一种很多新手第一反应会采用的做法暴力枚举。虽然最终代码用的是数学公式但理解暴力解法能让你更深刻地体会到“为什么需要最小公倍数公式”也能帮你在考场上没有思路时找到一条保底路径。6.1 暴力枚举思路从 n 1 开始一个一个往上试判断 n 是否能同时被 a、b、c 整除第一个满足条件的 n 就是答案。代码写起来非常直观a, b, c map(int, input().split()) n 1 while True: if n % a 0 and n % b 0 and n % c 0: print(n) break n 1这个做法在数据范围很小的时候完全可行。比如“2 4 5”n 从 1 试到 20 就能找到答案枚举次数不多。但如果三个数都很小比如“1 1 1”答案 1 也能瞬间找到。问题在于最坏情况如果三个数是三个很大的互质数比如“99991 99989 99971”答案大约是 10 的 15 次方量级暴力枚举会跑到天荒地老。这就是为什么数学解法在竞赛中如此重要——它把时间复杂度从 O(n) 降到了 O(log min(a, b))。对比一下暴力枚举和公式解法的边界情况。暴力枚举本质上是在“从小到大验证”它天然能找到最小公倍数不会出现“直接相乘”那种错误。但它太慢了而且没有触及问题的本质。我一般建议新手先写暴力版本验证自己对题意的理解是否正确再切换到数学解法提交这样能减少因题意理解偏差导致的无效提交。6.2 两种解法的时间复杂度对比解法时间复杂度适用范围暴力枚举O(LCM(a,b,c))数据范围极小仅适合验证思路辗转相除法求 LCMO(log min(a, b))任意正整数范围竞赛首选暴力解法在核桃这道题上不会超时因为题目数据范围不大。但在真正的竞赛里这种 O(n) 甚至更高复杂度的写法经常会被卡死。从暴力到数学优化的过程正是算法思维成长的过程。6.3 竞赛环境下的输入输出细节最后提一下输入输出的坑。蓝桥杯的评测系统对输出格式要求非常严格多一个空格、少一个换行都可能导致 Presentation Error。核桃这题只需要输出一个整数很多同学在输出时习惯加一个空格比如cout ans endl;这在普通 IDE 里看不出问题但在评测系统里就会被判错。正确做法是只输出整数加换行不要画蛇添足。还有一点读入三个整数时题目给出的输入格式是同一行里用空格隔开但也有可能用换行隔开。所以代码里用cin a b c或者input().split()都是稳妥的它们天然支持换行和空格混合的分隔方式。我个人在实际操作中的体会是像核桃的数量这种题目代码写起来不足十五行但它考察的读题能力、数学抽象能力和 ACM 式输出规范意识恰恰是很多同学刚刚接触竞赛时最欠缺的。先把这道题吃透再往后刷“最大公约数”“最小公倍数”相关的进阶题目时会顺畅很多。最后再分享一个小技巧每做完一道题不管多简单都顺手写一行注释记录自己当时的思路和踩过的坑几个月后回头翻看那本笔记比任何题解都值钱。