CSP-J 入门级 · CSP 2019 入门级第一轮 第 10 题

$319$ 和 $377$ 的最大公约数是（）。

这题考最大公约数，拿到数字先别急着死算，想想辗转相除法的步骤，或者观察两个数能不能被同一个质数整除。

很多同学容易在辗转相除的第二步算错余数，比如把319除以58算出5余29，却误以为余数是别的数，或者在分解质因数时漏掉公因数29，导致误选27或31。

考察知识点：最大公约数 — 辗转相除法（欧几里得算法）与质因数分解。

概念定义：辗转相除法的核心思想是 gcd(a, b) = gcd(b, a mod b)，即两个数的最大公约数等于较小数与两数相除余数的最大公约数，直到余数为 0，最后的除数就是最大公约数。另一种方法是分解质因数，取所有公共质因数的乘积。

命题视角：命题人喜欢用两个看起来毫无关联的数（319 和 377 都是三位数，且不是常见的倍数关系）来考察学生对算法的熟练度。他们往往会在中间步骤设置陷阱，比如让余数刚好是选项中的某个数，诱导学生直接选那个余数。

思考心法：拿到题先判断是用辗转相除还是分解质因数。这两个数比较大，分解质因数不容易一眼看出来，所以首选辗转相除。步骤如下： 1. 交换顺序，让大的做被除数：gcd(319, 377) = gcd(377, 319)。 2. 第一步除法：377 ÷ 319 = 1 余 58，所以 gcd(377, 319) = gcd(319, 58)。 3. 第二步除法：319 ÷ 58 = 5 余 29，所以 gcd(319, 58) = gcd(58, 29)。 4. 第三步除法：58 ÷ 29 = 2 余 0，所以 gcd(58, 29) = 29。

计算验证：为了保险，我们可以用分解质因数再核对一下。 319 = 11 × 29。 377 = 13 × 29。 公共质因数只有 29，所以最大公约数确实是 29。

避坑：这道题最容易错的地方是第二步的余数计算。319 ÷ 58，很多学生会算成 5 余 29，这是对的，但有人会粗心算成 5 余 31（选项 D），或者算成 5 余 27（选项 A）。一定要仔细检查乘法：5 × 58 = 290，319 - 290 = 29，没错就是 29。另外，看到 29 这个结果，很多同学会直接选，但要注意题目问的是“最大公约数”，不是“余数”，虽然这里余数 0 出现前的一步余数刚好是答案，逻辑上是通的，但概念要分清。

考频与趋势：根据题库数据，数论基础（含最大公约数）在 2009-2026 年间共考过 32 题，覆盖面很广。其中 2025 年考了 13 题，2024 年考了 7 题，2026 年考了 3 题，说明近两年的考频非常高，尤其是 2025 年几乎是一个小高峰。在分赛事分布上，GESP 五级考了 20 题，占比超过一半，说明这类基础算法在等级考试中是高频考点。CSP 入门级只考了 1 题，但考虑到入门级题目通常较简单，这道题作为单选题，难度适中，符合入门级定位。

预测：基于数据趋势，2025-2026 年数论类题目考频显著上升，且 GESP 五级持续占据主导地位，未来这类题目（尤其是辗转相除法的应用）在 GESP 五级、CSP 入门级以及 NOIP 普及组初赛中仍将是必考内容。命题人可能会继续用两个看似无关联的数来考察，或者增加一步辗转相除的变式（如求最小公倍数）。暂无足够依据预测具体年份的考题形式，但建议重点复习辗转相除法的步骤和易错点。