NOIP 普及组初赛 · NOIP 2009 普及组初赛试题 第 23 题

阅读程序写结果：

#include <iostream>
using namespace std;

int a,b;

int work(int a,int b){
	if (a%b)
		return work(b,a%b);
	return b;
}

int main(){
	cin >> a >> b;
	cout << work(a,b) << endl;
	return 0;
}

输入：20 12

拿到题先别急着模拟，一眼认出这是欧几里得算法（辗转相除法）求最大公约数。核心就是不断用余数替换大数，直到余数为0，剩下的那个数就是答案。

学生最容易栽跟头在两个地方：一是死记硬背公式却不懂递归终止条件，看到 a%b 就以为永远循环；二是模拟时粗心，比如算 8%4 时误以为非零继续递归，导致算出错误结果。这道题虽然简单，但考的是对算法本质的理解，而不是机械计算。

考点与命题视角

这道题考查的是递归函数与最大公约数（GCD）的算法实现，具体就是欧几里得算法（辗转相除法）。命题人特别喜欢用这种经典算法的变体来测试学生对递归逻辑的理解，而不是单纯考公式记忆。

在递归函数这块，题库里一共考了 115 题，覆盖从 2007 到 2026 年的所有级别，尤其是最近两年考得特别猛：2024 年有 25 题，2025 年有 15 题，2026 年也有 18 题。分赛事来看，GESP 五级考了 35 题，CSP 入门级考了 32 题，说明入门阶段对递归的考查非常密集。整数与整除的考点虽然只有 9 题，但最大公约数相关却高达 32 题，且 2025 年单年就有 13 题，2024 年 7 题，这组数据明显在凑数，命题人显然在刻意加大这类算法题的分量。

算法主线：欧几里得算法

欧几里得算法的核心思想很简单：两个数 a 和 b 的最大公约数，等于 b 和 a 除以 b 的余数（a%b）的最大公约数。用递归式写就是：

\[ \text{gcd}(a, b) = \text{gcd}(b, a \% b) \]

当余数为 0 时，递归终止，此时的 b 就是最大公约数。

看代码里的 work 函数：

int work(int a, int b) {
    if (a % b)          // 如果 a % b 不为 0（即余数存在）
        return work(b, a % b);  // 递归调用，交换参数
    return b;           // 否则返回 b
}

这里有个细节：if (a % b) 在 C++ 里等价于 if (a % b != 0)，因为非零整数的布尔值为真。所以只要余数存在，就继续递归；一旦余数为 0，直接返回当前的 b。