蓝桥杯的真题里有些题一看就知道考什么比如搜索、动态规划、图论但还有些题表面是个生活场景骨子里其实是一道数论题甚至可以说是在考察最基础的数学思维。这道2013年第四届的真题“核桃的数量”就是非常典型的一道。很多人在考场上第一眼会以为它是个模拟题甚至有人会想用枚举硬算但只要你真正理解了题目背后的数学模型会发现这题的代码量极小核心逻辑就几行真正的价值在于你能不能从“三只松鼠分核桃”这个故事里抽取出“求三个数的最小公倍数”这个本质。这篇文章就来完整拆解这道题从题目模型分析、数论原理、代码实现到同类题目的识别技巧一次性讲透。1. 题目背后真正考的是什么从分核桃到最小公倍数1.1 原题情境与输入输出规则题目大意是有三只松鼠主人每天给他们分核桃。第一只松鼠每天吃的核桃数是一个固定值第二只、第三只也各有自己的固定食量。但主人有个习惯每天都希望把核桃分成“正好能让三只松鼠各自吃饱”的份数也就是核桃总数必须能同时被三只松鼠的食量整除并且还要尽量少不能浪费。实际题目里是给出三个正整数 a、b、c分别代表三只松鼠每天吃的核桃数量要求输出一个正整数表示满足条件的最少核桃总数。输入在一行三个整数之间用空格隔开。输出一个整数。题目没有给特别刁钻的数据范围但按照蓝桥杯早期真题的惯例一般三个数的范围都在 1 到 30 之间也就是说哪怕你用最简单粗暴的枚举法从 1 一直试到某个上限也完全能在规定时间内跑完。但这道题的价值恰恰在于它允许你用笨办法通过但如果你只会笨办法说明你还没具备“从题目文字中抽象数学模型”的能力。竞赛里最重要的不是“这题我能不能过”而是“我能不能一眼看出它在考什么”。1.2 为什么问题的本质是求最小公倍数我们换个角度想。核桃总数要同时满足三个条件能被 a 整除、能被 b 整除、能被 c 整除。也就是说这个数必须是 a 的倍数也必须是 b 的倍数还必须是 c 的倍数。如果你学过集合论的概念可以把这三个条件看成三个集合的交集这个数需要落在“a 的倍数集合”、落在“b 的倍数集合”、落在“c 的倍数集合”里。三个集合的交集就是一个又一个共同倍数。题目还要求“数量最少”那自然就是找这些共同倍数里最小的那一个。这不就是最小公倍数Least Common Multiple简称 LCM的定义吗两个数的最小公倍数是能同时被这两个数整除的最小正整数三个数的情况就是把它推广到三元。所以这题的数学模型就是求 LCM(a, b, c)。有朋友可能会问为什么不可能是最大公约数很简单最大公约数是能同时整除这几个数的最大数它是“分给别人”的粒度而不是“总数量”。核桃总数是被分的对象它必须大到能容纳下每一种食量所以方向是“倍数”而不是“约数”。1.3 枚举法为什么能过但不应该成为首选假设你第一次见到这题还没学辗转相除法最朴素的做法是从 1 开始往上枚举逐个判断这个数能否同时被 a、b、c 整除。写成伪代码大概是def brute(a, b, c): i 1 while True: if i % a 0 and i % b 0 and i % c 0: return i i 1这种解法在 a、b、c 都很小的时候比如 2、3、5答案是 30枚举 30 次就出结果了毫无压力。就算三个数都是 30它们的最大公约数是 30最小公倍数也是 30枚举 30 次也能过。这个数据范围决定了很多不完美的解法也能得分。但为什么我不建议你把枚举当作这题的标准解法原因有三点第一它没有触及数学本质。竞赛的价值在于训练思维如果你满足于“循环加 if”那遇到数据范围放大到 10^9 的同类题时你会直接懵掉。第二它存在一个隐藏的循环边界问题。如果三个数里有互质的组合比如 7、11、13答案会到 1001枚举次数还在可接受范围但如果换成 97、89、83答案会达到几十万甚至更多虽然单次判断很快但你已经处在“靠天吃饭”的状态了。第三蓝桥杯的评测数据虽然简单但作为一个有追求的选手你应该把每题都当成练习题来做而不是当成“混分题”来做。后面你会发现用数论方法实现的核心代码只有一行。这才是这道题想传达给你的东西数学建模能力比码力更值钱。2. 最小公倍数怎么算辗转相除法与公式推导2.1 先用最大公约数搭桥要求三个数的最小公倍数第一反应肯定是先学会求两个数的。两个数 a、b 的最小公倍数和最大公约数之间有一条非常重要的关系LCM(a, b) * GCD(a, b) a * b也就是说LCM(a, b) a * b // GCD(a, b)这个式子很好验证。比如 a4b6GCD 是 2那么 LCM 4 * 6 / 2 12而 12 确实是 4 和 6 的最小公倍数。为什么这条关系成立你可以这样理解a 和 b 的乘积里公共因子部分被重复计算了一遍。最大公约数正好代表了这堆公共因子所以除以一个 GCD就把重复的部分去掉了。这就像两个人合租一套房房租是每个月 4000 元其中公共区域的水电费公共因子被两个人各算了一次除以 GCD 就是把多算的那部分拿掉。有了这个公式问题就从“求最小公倍数”转化成了“求最大公约数”。而求最大公约数正是我们熟悉的欧几里得算法辗转相除法的看家本领。2.2 辗转相除法的原理与证明思路辗转相除法的核心思想非常朴素用较大的数除以较小的数再用除数除以余数重复这个过程直到余数为 0此时的除数就是最大公约数。用数学语言描述就是GCD(a, b) GCD(b, a mod b)其中 a b为什么这样迭代能成立可以简单证明一下。设 a b * q r其中 r 是 a 除以 b 的余数。那么任何能同时整除 a 和 b 的公约数 d一定也能整除 r因为 r a - bq所以 d 也是 b 和 r 的公约数。反过来任何能同时整除 b 和 r 的公约数也一定能整除 a。因此 a 和 b 的公约数集合与 b 和 r 的公约数集合完全一致它们的最大公约数自然也就相等。这就像你在整理一堆杂物先把最大的箱子拆开取出能放进小箱子的部分剩下的继续拆。每次操作都在缩小问题的规模但公约数的“本质”没有变。最终当余数为 0 时最大的那个箱子就是所有箱子尺寸的公约数。用代码写出来就是int gcd(int a, int b) { while (b ! 0) { int temp b; b a % b; a temp; } return a; }或者写成递归版本更简洁int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); }这段代码我建议你背下来但更重要的是理解它为什么对。理解了之后哪怕你哪天真忘了也能现场推导出来。2.3 从两个数扩展到三个数两个数的最小公倍数解决之后三个数怎么办答案是分两步走。先求前两个数的最小公倍数再拿这个结果和第三个数求最小公倍数。LCM(a, b, c) LCM(LCM(a, b), c)这个结合律是数学上天然成立的因为“倍数”这个概念本身就有传递性。类比一下你先找到能同时满足松鼠一和松鼠二的核桃数再把这个数放到松鼠三的条件里筛选如果它连松鼠三也能整除那它自然是三者的共同倍数取最小就是三者共同倍数里的最小值。用代码来表示就是int lcm(int a, int b) { return a / gcd(a, b) * b; // 注意先除后乘防止溢出 }然后主程序里调用两次int result lcm(lcm(a, b), c);这里有一个非常关键的编程细节我在写 lcm 函数时用的是a / gcd(a, b) * b而不是a * b / gcd(a, b)。虽然数学上两者等价但在计算机里a * b可能先算出一个超大数导致整数溢出。先除后乘能把中间结果控制在更小的范围内。这是实战中很多人会踩的坑尤其是当题目数据范围一旦放大溢出造成的错误非常隐蔽程序不会报错只是答案莫名其妙地不对。2.4 一个容易混淆的点乘积除以最大公约数会不会出现整除问题有朋友可能会担心既然 GCD(a, b) 不一定能整除 a那a / gcd(a, b)会不会出现小数答案是不会。因为最大公约数本身就是 a 的约数所以它一定能整除 a。事实上a / gcd(a, b)得到的是“去掉 a 和 b 的公共因子后a 剩下的部分”这一步做完再乘以 b就能得到最小公倍数。举个例子a12b18GCD 是 6。先算 12 / 6 2再算 2 * 18 36这就是 12 和 18 的最小公倍数。你要是倒过来先算 12 * 18 216再除以 6 也能得到 36但中间那个 216 已经比最终结果大了好几倍。3. 完整代码实现与细节打磨3.1 C语言标准解法蓝桥杯默认支持 C/C我推荐用 C 语言写因为简单直接、运行速度快。先看完整代码#include stdio.h int gcd(int a, int b) { while (b ! 0) { int temp b; b a % b; a temp; } return a; } int lcm(int a, int b) { return a / gcd(a, b) * b; } int main() { int a, b, c; scanf(%d %d %d, a, b, c); int ans lcm(lcm(a, b), c); printf(%d\n, ans); return 0; }这段代码放在任何 OJ 上都能直接通过。我们来逐段拆解scanf(%d %d %d, a, b, c);读取三个整数这里不用管换行符的问题%d会自动跳过空白字符。lcm(lcm(a, b), c)先算 a 和 b 的最小公倍数再与 c 计算。注意内层 lcm 的结果作为外层 lcm 的第一个参数。printf(%d\n, ans);输出答案记得加换行否则在某些严格判题的 OJ 上可能出现 Presentation Error。3.2 Python 解法与标准库的对比如果你参加的是蓝桥杯 Python 组代码可以更简洁。Python 自带的math模块里虽然没有直接的 lcm 函数但在 Python 3.9 之后的版本里有math.lcm。不过比赛环境不一定是最新版本所以我建议自己写顺便把算法原理体现出来import math def lcm(a, b): return a // math.gcd(a, b) * b a, b, c map(int, input().split()) ans lcm(lcm(a, b), c) print(ans)这里用//做整数除法也是为了避免浮点数精度问题。如果你用/再转int在数值很大的时候可能因为浮点数溢出而出现误差虽然这题数据范围小不容易触发但养成好习惯很重要。3.3 边界情况与自测用例写算法题最怕的不是思路不对而是细节没照顾到。我建议你提交之前至少跑一遍下面这些测试用例输入输出说明1 1 11所有数都是 1最小公倍数是 12 3 530两两互质答案直接是乘积4 6 824有公因子 2不是简单乘积12 18 30180公因子较多考验 LCM 计算的正确性30 30 3030三个相等最小公倍数等于本身把这几组数据跑通了代码基本稳了。特别是第一组“1 1 1”很多人容易忽略边界值比如用枚举法写while时初始化不当可能导致死循环或多算一次都得留意。3.4 一个小优化多个数的最小公倍数可以循环处理如果你以后遇到“输入 n 个数求它们的最小公倍数”的题目可以把这段逻辑改成循环int ans 1; for (int i 0; i n; i) { scanf(%d, x); ans lcm(ans, x); }初始值设成 1是因为 1 和任何数的 LCM 都是那个数本身。这个写法非常通用建议记住。它和“累乘”是两回事——如果你天真地把所有数乘起来再除以最大公约数遇到多个数的情况往往算不对因为多个数的最大公约数不是两两 GCD 的简单组合。而用循环逐步合并每次都是严格的二元运算逻辑就完全正确。4. 同类考题的识别技巧与思路迁移4.1 怎么一眼看出题目在考 LCM刷题多了你会发现很多题并不会直接告诉你“求最小公倍数”而是披着各种外衣。常见的包装方式有轮流工作甲每隔 a 天来一次乙每隔 b 天来一次问多少天后两人同时来。分东西一箱水果能同时被 a 个一组、b 个一组、c 个一组分完至少多少个。齿轮咬合三个齿轮齿数分别是 a、b、c问转多少圈后同时回到初始位置。路灯编号从 1 到 n 的整数中同时是 a 和 b 的倍数的有哪些求最小那个。这些场景的共同点就是“同一个对象需要同时满足多个整除条件”而“最小”二字出现时基本就是在呼唤 LCM 了。你只要在解题时先问自己一句这个题是要求一个数还是求多个数求的这个数和给定的数之间是什么关系如果答案是“给定数的共同倍数中最小的”它就是 LCM。4.2 和 GCD 家族其他题型的对比顺便帮你梳理一下 GCD 家族的常见变体避免考试时把概念弄混。题型特征词本质典型问法求最大公约数最大、公共约数、都能被它整除GCD(a, b)一块地能切成最大多大的正方形求最小公倍数最小、同时被整除、共同倍数LCM(a, b)核桃总数最少多少个裴蜀定理整数解、线性组合gcd 与组合的关系ax by c 是否有整数解扩展欧几里得模逆元、不定方程exgcdax ≡ 1 (mod b) 求 x这张表帮助你建立知识网络。当你看到一个数论题时先把它归类再去想对应的算法会快很多。4.3 从这题延伸出的进阶思考题如果你觉得这题已经做透可以试试下面的思考题如果题目改成“求最小的能被 1 到 20 中所有数整除的数”怎么算这其实就是 Project Euler 的第 5 题答案是 232792560。你需要用到循环合并 LCM 的技巧而不是一次性枚举。如果 a、b、c 的范围变成 10^18你怎么保证先除后乘不会溢出此时可能需要用到高精度或者 Python 这种大整数语言。如果题目要求的不只是“数量最少”而是“在不超过 N 的前提下数量最大且满足条件”那问题就变成了约束条件下的 LCM 搜索复杂度会完全不一样。这些延伸问题不用现在全部实现但可以留个印象等学到更多数论知识后再回来验证。5. 现场答题容易踩的坑与我的实操经验5.1 最容易被忽略的坑输入里可能有多余空格或换行蓝桥杯的输入一般很规范但也不能排除评测数据里行末有多个空格或者最后一行没有换行。用scanf和input().split()都能自动处理只要别用gets、readline后忘记strip问题不大。如果你用 Python我推荐写成a, b, c map(int, input().split())而不是先读一行再用split( )拆因为后者遇到连续多个空格时会拆出空字符串导致 ValueError。用默认的空格分割方式能自动压缩连续空白符。5.2 输出格式换行符是隐性要求在本地测试时你有没有加换行可能感觉不到区别因为终端显示时无所谓。但在 OJ 的判题系统里有时候答案文件是逐字符比对的少了换行可能判 WRONG ANSWER。我一般在printf里都带上\nPython 的print天然带换行不用额外操心。5.3 时间复杂度与空间复杂度这道题的 po 点在于GCD 的计算复杂度是 O(log(min(a, b)))非常快几乎可以认为是常数时间。哪怕是 10^18 级别的整数辗转相除法也只需要几十次迭代。空间复杂度更是 O(1)只用了几个变量。所以在蓝桥杯这个量级下完全不用担心超时。我见过有些朋友用枚举法写完之后还专门优化了step比如每次加 a 的倍数而不是加 1虽然这也是个可行的优化思路但比起 GCD 解法来说还是绕了远路。学到这个阶段你需要的不是优化一个笨办法而是直接换一条聪明的路。5.4 我参加练习赛时的真实感受我第一次做这题的时候其实也不是秒杀。当时我在纸上画了半天想“是不是要用动态规划”还尝试把三个数的最小公倍数拆成“两两 LCM 再 LCM”但又怀疑是不是要多考虑一些情况。后来我拿 4、6、8 这个例子手动验证发现先算 LCM(4,6)12再算 LCM(12,8)24结果正确又用枚举法暴力跑了一遍确认才完全放心。所以我的经验是学数论题不要怕“我觉得对但不确定”。最好的验证方式就是小范围枚举 数学推导交叉验证。跑出同一个答案之后你对这个公式的信任度会大幅提升之后遇到变体也敢直接用。这道题虽然简单但它是一个非常好的“模型题”题目故事化、数据温和、算法经典。如果你能把它的思路讲给别人听并且能在白板上默写出 gcd 和 lcm 的代码那么你对基础数论这一块就算建立了正确的直觉。后面再去学扩展欧几里得、中国剩余定理都会觉得顺理成章。