刷 OpenJudge-NOI 的 2.2 基本算法章节时7592 题“求最大公约数问题”看起来是那种热身级别的题目题面短、数据范围小、算法经典好像两三分钟就能交上去。但它偏偏被放在“递归和自调用函数”这个单元里这说明出题人想让你做的不是单纯算出答案而是用递归的眼光去重新认识一个从小学就接触过的数学概念。我带过的学生里不少人都能用辗转相除法秒掉这道题但被问到“为什么递归出口是 b 0”“为什么 gcd(a,b) 能变成 gcd(b, a%b)”时反而开始卡壳。这篇文章就把 7592 从数学原理、递归写法、评测细节到实际踩坑完整拆一遍希望能帮你把这道题吃透而不是停留在“能 AC”这个层面。1. 题目拆解7592 到底在考什么1.1 题面与输入输出要求题目要求非常简单输入两个正整数输出它们的最大公约数。这是数学里的基础概念——能同时整除这两个数的最大正整数。比如 12 和 8 的最大公约数是 4因为 12 和 8 都能被 4 整除而没有任何比 4 更大的正整数具备这个性质。OpenJudge 上的输入输出格式通常是一行两个整数输出一个整数末尾要有换行。很多人第一次交这类题时会把重点全放在算法上忽略了输出格式结果本地运行完全没问题提交后却得到一个 WAWrong Answer。这道题的数据范围一般在 int 之内所以算法上的时间压力很小真正的考察点是递归结构而不是常数优化。1.2 为什么它被归入“递归和自调用函数”单元如果把题目当成一道普通数学题用短除法分解质因数也能求最大公约数。但它被放进递归章节是因为最大公约数的求解过程天然具有“自相似”结构要求 gcd(a,b)可以先把它转化为 gcd(b, a % b)问题从“两个大数的最大公约数”变成“两个更小的数的最大公约数”然后继续转化直到其中一个数变成 0。这就是递归的核心雏形一个函数在处理问题时把当前问题化简为规模更小的同类问题然后调用自己每次调用都带着新的参数直到某个条件满足时不再调用自己直接返回结果。这个“自己调用自己”的行为在 C/C 里就叫自调用函数。7592 最妙的点在于它把递归三要素压缩在一个函数里自调用、规模递减、明确的出口。2. 辗转相除法的数学本质为什么它能递归2.1 从短除法到欧几里得算法小学阶段求最大公约数最常用的是短除法把两个数分别分解质因数再提取公共因子相乘。比如求 24 和 36 的最大公约数24 2³ × 336 2² × 3²公共部分是 2² × 3 12所以答案是 12。这个方法好在直观但坏在必须依赖质因数分解。一旦数字变大质因数分解本身就是一件非常麻烦的事。假如给你两个接近亿级的数让你手工分解能直接做崩溃。欧几里得算法也叫辗转相除法绕开了质因数分解它的思路是反复用较大的数对较小的数取模把问题规模大幅缩小。比如求 48 和 3648 % 36 1236 % 12 0当余数为 0 时当前的除数 12 就是最大公约数整个过程只需要几次取模运算完全不需要分解质因数。这就是为什么它能在计算机算法里站稳脚跟。2.2 关键恒等式gcd(a,b) gcd(b, a mod b)这个恒等式是整个算法的灵魂。如果你只记住代码不理解它遇到变式题就容易翻车。先说结论a 和 b 的最大公约数等于 b 和 a%b 的最大公约数。证明思路也不复杂。假设 a k × b r其中 r a % b那么 a 是被除数b 是除数k 是商r 是余数。如果某个整数 d 能同时整除 a 和 b那么 d 也一定能整除 a - k × b。由于 a - k × b r所以 d 能整除 r。反过来如果 d 能同时整除 b 和 r那么 d 也一定能整除 k × b r也就是 a。这样一来a 和 b 的公共因子集合与 b 和 r 的公共因子集合完全一致。两个集合的最大元素自然相同所以最大公约数也相同。这个恒等式最漂亮的地方在于它保证递归的规模一定会变小。因为 a % b 严格小于 b所以每一轮递归里函数的第二个参数都会变小最终会到达某个参数为 0 的基准情况。这正是递归能结束的前提。2.3 更相减损术的铺垫为什么取模比连续减法更高明中国古代数学里有一种类似思路叫更相减损术如果 a b那么 gcd(a,b) gcd(a-b,b)。逻辑上它没有任何问题因为公共因子同样能整除差值。但它有个致命弱点极端情况下效率太低。比如求 gcd(1, 10000)按更相减损术每次只能从 10000 里减掉 1需要减 9999 次才能碰到 gcd(1,1)1。而用辗转相除法10000 % 1 0一步就得到答案。取模相当于一次执行多次减法压缩了整个递归过程。这两种算法的对比非常值得记下来算法核心操作求 gcd(1, 10000) 需要的步骤更相减损术a a - b9999 次减法欧几里得算法a a % b1 次取模这也是一个很好的提醒递归本身不保证高效关键在于你的递归转化是否把问题规模压缩得足够快。3. 代码怎么写递归函数与提交细节3.1 最小可提交的递归实现理解了恒等式写代码就顺理成章了。我用 C 实现了最标准的版本#include cstdio int gcd(int a, int b) { if (b 0) { return a; } return gcd(b, a % b); } int main() { int a, b; scanf(%d%d, a, b); printf(%d\n, gcd(a, b)); return 0; }这段代码里gcd 函数完全遵循递归三要素当 b 为 0 时直接返回 a这是出口否则把问题转化为 gcd(b, a % b)这是自调用同时也是规模递减的转化。主函数负责读入和输出完事。有些人喜欢把整个函数压成一行int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); }这种写法看起来很简洁但不建议作为学习阶段的习惯。原因很简单递归调用的逻辑已经很隐晦了再用三元运算符压缩出错时排查反而困难。竞赛做题求快可以这么写作为学习展开写更清楚。3.2 递归出口为什么是 b 0而不是 a 0这是初学者最容易迷糊的点。你可以这样理解当余数为 0 时说明当前这一层的除数已经能整除被除数了那这个除数就是两个原始数的最大公约数。看一个具体链路gcd(48, 36)48 % 36 12所以转化为 gcd(36, 12)36 % 12 0所以转化为 gcd(12, 0)b 现在是 0gcd(12, 0) 12也就是说出口条件最终卡在“第二个参数变成 0”的那一刻。为什么不是“第一个参数变成 0”因为递归转化的方向是 gcd(b, a%b)新调用的第二个参数是上一轮的余数。余数为 0 是算法结束的数学标志此时最大公约数已经确定就是当前的除数 a。3.3 OpenJudge 平台的输入输出与评测纪律这道题是在 OpenJudge 上评测的所以必须遵守在线评测的规则。输入从标准输入读输出写到标准输出不需要打开任何文件。代码里 scanf 的格式串写成了 %d%d中间没有空格这也是合法的因为 %d 会自动跳过输入中的空白字符包括空格、tab 和换行。输出要用 printf(%d\n, gcd(a, b))末尾的换行不能省。很多 OJ 会把输出结果逐字符比对缺一个换行、多一个空格都可能判 WA。有些同学习惯先在本地用 cout 调试提交时忘改输出格式这种低级失误最可惜。我在实战中一般建议用 cstdio 而不是 iostream。原因倒不是因为这道题的性能差距有多大而是长期来看scanf/printf 的格式化能力更强读取大输入时也更稳而且不会出现 cin/cout 因为关闭同步不及时导致的性能问题。等你后面做到需要读大量数据的题目时会感谢这个习惯。当然如果在本地用 C17 甚至更高版本cin/cout 也完全够用只是 NOI 系列赛事中保守点没坏处。4. 递归调用过程拆解以 12 和 8 为例看函数栈4.1 一步步拆开 gcd(12, 8) 的调用链纸上谈兵不如动手走一遍。假设输入是 12 和 8程序调用 gcd(12, 8)。下面这张表展示了每一层发生的事情调用层次当前 a当前 ba % b下一步第 1 层1284调用 gcd(8, 4)第 2 层840调用 gcd(4, 0)第 3 层40不计算触发 b 0返回 4关键点在于第 3 层返回的 4 并不是直接回到主函数而是先回到第 2 层第 2 层接到这个返回值后自己立即返回 4第 1 层也是如此。最后主函数才拿到最终结果 4。这就体现了“递”和“归”两个阶段。“递”是不断向下调用直到碰到出口“归”是从出口一层层把结果带回来。很多初学者只看到“递”的链条忽略了“归”的方向所以总觉得自己理解了递归但一画调用过程就露馅。4.2 自调用函数的栈帧模型为了理解为什么每一层的 a、b 不会互相干扰我用一个“盒子”类比。每次调用 gcd 函数程序都会在内存的调用栈上开一个新盒子里面装着这一层自己的 a、b 变量。盒子和盒子之间的同名变量互不相干。第 1 层的 a 是 12b 是 8第 2 层的 a 是 8b 是 4。虽然名字都叫 a 和 b但它们放在不同的盒子里。递归调用完成后最底层的盒子先被回收返回值传递给上一层的盒子上一层盒子也随后被回收。这种“后进先出”的顺序和栈结构完全一致。如果你觉得抽象可以想象一队人从前排往后排传石头第一个人把石头递给第二个第二个递给第三个直到最后一个人拿到石头后再原路一个传一个传回第一个人。递归的返回值就是这样一层层“归”上来的。4.3 为什么这段递归不会把栈压爆有人一听到递归就担心栈溢出。其实欧几里得算法的递归深度非常浅。最坏情况出现在两个连续斐波那契数之间比如 gcd(144, 89)。斐波那契数列是递归次数最多的输入但即便如此递归层数也只和数字大小呈对数关系。对于 int 范围内的整数递归深度通常不会超过几十层离系统栈上限还远得很。真正把栈压爆的情况基本都是递归没写出口或者出口条件永远无法满足。这个坑下面单独说因为它几乎是所有递归初学者都会踩到的坎。5. 新手踩坑实录边界条件、死循环与评测 WA5.1 漏掉 b 0 的后果不只是无限递归最常见的错误写法长这样int gcd(int a, int b) { return gcd(b, a % b); }看起来像那么回事问题在于当 b 是 0 时a % b 就是整数除以 0这在 C/C 中是未定义行为。轻则程序崩溃重则直接返回一个随机值。如果某些输入恰好没触发除零程序可能侥幸跑出正确结果一旦 b 变成 0等待你的就是 Runtime Error。我见过不少学生把递归出口写在注释里实际代码却忘了加交上去直接 RE然后一脸茫然。所以检查递归函数时第一眼看的就是出口条件写没写对有没有可能在某个时刻跳过出口。5.2 递归转化方向的错误还有一类错误是把递归式子写反了比如int gcd(int a, int b) { if (b 0) return a; return gcd(a % b, b); }表面上看只是交换了参数顺序但实际执行时如果 a ba % b a下一层调用变成 gcd(a, b)参数完全没变于是进入无限递归最后栈溢出。写成 gcd(b, a % b) 就保证了每次第二个参数都变成严格更小的余数递归链条一定会走向 b 0。这个细节很值得在纸上画两笔比背代码有效得多。5.3 输出格式和数据范围问题本题输入是两个正整数数据范围在 int 内但这不代表可以掉以轻心。我遇到过有人把输出写成 printf(%d, ans) 之后少打换行也遇到过 scanf 忘了写取地址符写成 scanf(%d%d, a, b)。前者是 WA后者可能直接 RE。这些并不是算法问题却是 OJ 上最常见的送分题变送命题。另外有些题解里喜欢自以为是地写 while (scanf(%d%d, a, b) ! EOF)因为题目只有一组输入这个 while 循环只会执行一次也能 AC。但我一般不建议画蛇添足题目怎么要求输入就怎么读题目说只有一行就直接读两个数简单直接。5.4 函数名与标准库的冲突如果你本地的编译器比较新并且在代码里写了 using namespace std有自己的 gcd 函数同时恰好包含了 那么在一些 C17 环境下会出现函数名歧义因为标准库里也有 std::gcd。编译错误信息经常是 call to gcd is ambiguous新手看到这个错误会非常困惑。解决方法有三种不写 using namespace std或者把自己的函数命名为 mygcd或者直接用标准库的 std::gcd。不过在 OpenJudge 和 NOI 系列环境中C 标准通常不是 C17标准库没有 std::gcd所以自己写 gcd 函数完全没问题。但为了养成好习惯我还是建议本地别依赖 using namespace std尤其在写算法题时全局污染带来的麻烦远大于省几个字的便利。5.5 直接用循环做也能过为什么不推荐这道题用循环也能轻松 ACint gcd(int a, int b) { while (b ! 0) { int temp a % b; a b; b temp; } return a; }这个迭代版本在功能上完全正确甚至性能更好。但如果你正在刷“递归和自调用函数”章节就应该强制自己用递归写。因为章节训练的目标不是让这道题过而是让你通过这道题建立递归思维。等你后面遇到树的遍历、快速幂、汉诺塔、回溯搜索时会发现递归思维能不能建立起来直接决定了那些题能不能做出来。所以即便循环版本正确我也建议写完递归版本后再去对照循环版本体会两者的关系。6. 从 7592 延伸开去最大公约数的应用与递归扩展6.1 多个数的最大公约数实际题目不会只让你求两个数的 gcd很可能是给你一个数组求所有数的最大公约数。方法也简单从头到尾两两合并每次用当前的 gcd 去更新答案。int ans 0; for (int i 0; i n; i) { ans gcd(ans, a[i]); }这里 ans 初始化为 0 是有讲究的因为 gcd(0, x) x所以第一轮就能正确把第一个数带进来。这个初始化技巧在很多递推题目里都能用到。6.2 最小公倍数与 gcd 的关系求最小公倍数 lcm(a,b) 也离不开最大公约数公式是lcm(a,b) a / gcd(a,b) * b特别提醒一定要先除后乘。如果先算 a * b在大数据范围内可能直接溢出导致结果错误先做除法得到的结果一定整除乘出来就不会超过两个数乘积的数学范围。这是很典型的“看着很基础实际很多人踩”的坑。6.3 递归思维的跳板7592 是所有递归题的“最小样板”。从它延伸出去你会遇到快速幂的递归写法把 a^n 拆成 a^(n/2) 的平方会遇到汉诺塔问题把 n 个盘子的移动拆成 n-1 个盘子的移动会遇到二叉树的遍历先处理根再递归处理左右子树。这些题本质上都是同一个思维模型找到大小递减的子问题找到出口让函数自己调用自己。如果你能把 gcd(12,8) 的调用栈画清楚那快速幂的每一层递归也难不倒你。因为它们共享同一个底层机制函数调用栈、参数隔离、返回值回溯。我经常对学生说7592 不是一道“会了就行”的题而是一道“能讲明白才算会”的题。能用嘴巴说清楚每一层调用的参数变化比在编译器里跑出 AC 更有价值。最后分享一个我自己调试递归函数的小习惯如果递归结果总是不对别急着怀疑算法先在函数开头加一句调试输出比如 printf(gcd(%d, %d)\n, a, b);把每一层进入时的参数打出来。对 7592 这种题打印出三四行就能立刻看清递归方向对不对、出口有没有触发。调通之后记得删掉调试语句。这个习惯我从刷 OJ 初期一直保留到现在往后的树的递归、回溯搜索、动态规划记忆化搜索都靠这种“在递归入口打印参数”的方法快速定位问题。早期在简单题上多花几分钟熟悉调试手段后面解决复杂问题时会省下大量时间。