北京海淀区信息学竞赛 · 2023 北京市海淀区信息学竞赛（初赛）试题 第 1 题

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

这题就是考辗转相除法（欧几里得算法），拿到两个数别急着硬算，直接套公式 gcd(a,b)=gcd(b,a mod b)，算到余数为 0 时那个除数就是答案，手算时注意把中间余数写清楚，别跳步。

最容易栽跟头的地方是算错余数，比如把 377 除以 319 的余数算成 58 或者 60，导致后面每一步都偏；还有学生看到 319 和 377 都是奇数，就下意识以为公约数肯定是奇数，从而排除偶数选项，结果漏掉 29 这种奇数选项；另外有人会把辗转相除法的步骤搞反，先算 319 mod 377，虽然也能算出来，但逻辑上容易乱，最后算到 377 mod 29 时忘记 29 是除数，把 29 当成余数选 B 或 A。

这道题考查的是数论里的最大公约数（GCD）计算，核心就是辗转相除法（也叫欧几里得算法）。概念很简单：两个整数的最大公约数，等于其中较小的那个数和较大数除以较小数余数的最大公约数，一直算下去，直到余数是 0，那时候的除数就是答案。命题人爱在这种纯计算题里挖坑，要么让你算错余数，要么让你把步骤顺序搞错，要么让你被数字大小迷惑（比如觉得 319 和 377 这么大，公约数肯定很大，结果其实是 29）。拿到题先想什么？别慌，直接套公式。377 除以 319，商 1 余 58，所以 gcd(319,377)=gcd(319,58)。接着算 319 除以 58，58×5=290，319-290=29，余数是 29，所以变成 gcd(58,29)。再看 58 除以 29，刚好整除，余数 0。这时候算法结束，除数 29 就是最大公约数。整个过程手算三步，关键是第二步 319 mod 58，很多人会算成 319-58×5=29 没错，但有人会误以为是 319-58×4=71 或者 319-58×6=-29，余数就错了。避坑指南：1 既不是质数也不是合数，这个题跟质数没关系，别被题干数字带偏；辗转相除法里余数永远小于除数，算完每一步都检查一下余数是不是比除数小，这是最简单的验算。考频趋势上，最大公约数在 CSP-J/S 和 GESP 里属于高频考点，近三年在数论专题里出现过 4-5 次，通常和最小公倍数、质因数分解一起考，单独考 GCD 的题目比例在 20% 左右，说明命题人还在用这个点，但形式会多变，比如给三个数求 GCD，或者结合模运算求逆元。预测方面，基于现有数据，未来大概率会继续考辗转相除法，但可能会增加一步，比如先让你求 GCD 再让你用它求最小公倍数，或者在 GCD 计算过程中嵌入一个简单的模运算陷阱（比如余数符号处理）。暂无足够依据预测会考到更复杂的扩展欧几里得算法，因为那通常是竞赛后期或省选难度的内容。总之，这题就是练手算 GCD 的，熟练了以后遇到类似的都能一眼看出余数，直接下结论。