GESP 五级 · GESP202609 C++ 五级 第 18 题

下面欧几里得算法既适用于 a > b ，也适用于 a < b ，只要 a 、b 是正整数。

int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}

看到这类题先想算法不变量：gcd(a,b) = gcd(b, a%b)。迭代版每轮把(a,b)换成(b,a%b)，顺序天然翻转，所以 a<b 时第一轮就把大数放 a 里了。再想边界：b=0 时循环结束，返回 a，这正是 gcd(a,0)=a。最后想反例：有没有 a,b 正整数但算出来不是最大公约数？没有，因为每次替换都保持公约数集合不变。

选项 B 把"a>b 才成立"当成前提，这是把递归写法里的"先交换"误读成"必须 a>b"。实际上递归版 gcd(a,b) 里若 a<b 会先调用 gcd(b,a)，迭代版直接 a%b 就能处理。命题人故意用"只要 a、b 是正整数"来掩盖这个细节，诱导考生忽略取模运算对大小关系的自动调整。

考纲定位

本题对应《GESP 五级 C++ 算法基础》中"欧几里得算法"考点，属于数论与循环控制结合的综合题。命题人把它放在五级，是因为它既考察对算法不变量的抽象理解，又要求能准确判断迭代实现与递归实现的等价性，卡住的是那些只会背代码、不懂原理的考生。

解题思维

首先抓住核心不变量：gcd(a,b) = gcd(b, a%b)。无论 a 和 b 谁大谁小，这一等式都成立。迭代版每轮把(a,b)换成(b,a%b)，相当于把原来的 b 放到 a 的位置，原来的 a%b 放到 b 的位置。因此当初始 a<b 时，第一轮循环里 a%b 就是 a，b 变成 a，下一轮 a 就是原来的 b，顺序自动翻转，算法依然正确。边界情况 b=0 时循环终止，返回 a，符合 gcd(a,0)=a 的定义。

陷阱拆解

选项 B 的错误根源在于把"a>b"当成算法成立的前提。递归写法里，若 a<b 会先交换再递归，但迭代写法不需要显式交换，取模运算已经隐式完成了大小调整。命题人特意在题干里强调"只要 a、b 是正整数"，就是为了掩盖这个细节，诱导考生忽略取模对大小关系的自动处理。许多考生看到 a%b 就下意识认为 a 必须大于 b，从而误判算法只在 a>b 时有效。

反命题思维

如果把条件改成"仅当 a>b 时成立"，算法就需要在循环前加一次 if(a<b) swap(a,b); 否则第一轮 a%b 会直接得到 a，导致 b 变成 a，后续逻辑全乱。若改成递归版，则必须保证递归调用时参数顺序正确，否则会出现栈溢出或死循环。反过来，如果题目问"能否用递归实现"，答案依然是正确，因为递归版同样依赖不变量，只是多了函数调用开销。这种变式能进一步检验考生对算法本质的把握。