GESP 五级 · GESP 202506 C++ 五级 第 16 题

下面 C++ 代码是用欧几里得算法（辗转相除法）求两个正整数的最大公约数，$a$ 大于 $b$ 还是小于 $b$ 都适用。

int gcd(int a, int b) {
    while (b) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

辗转相除法求最大公约数：gcd(a,b) = gcd(b, a%b)，当b=0时返回a。时间复杂度O(log min(a,b))。

辗转相除法中gcd(a,b)和gcd(b,a)结果相同。注意a和b的顺序不影响结果。

【考点】欧几里得算法｜循环控制｜变量交换

🎯 考纲定位：GESP 五级《算法与数据结构》模块核心考点。命题人专卡"数学知识到代码实现"的转化断层——很多学生背得熟 gcd(a,b)=gcd(b,a%b) 公式，却写不出正确的迭代过程，这道题就是筛掉只会理论不会落地的考生。

🧠 解题思维：欧几里得算法本质是不断用余数替换较大数。代码里 while(b) 保证循环直到 b=0，此时 a 即为最大公约数。关键观察是每次循环先暂存 b 到 temp，再把 a%b 赋给 b，最后 temp 赋给 a——这步"暂存-赋值"正是实现变量交换的暗线。若 a<b，第一次循环 a%b 等于 a，b 变为 a，a 变为原 b，自动完成大小互换，无需额外判断。

🪤 陷阱拆解：选项 B 的错误思维来自三个常见误区。一是误以为 a%b 在 a<b 时无意义，其实余数定义对任意正整数都成立；二是忽略 temp 的必要，若直接写 b=a%b;a=b 会导致 b 被覆盖后 a 拿不到旧 b 的值；三是混淆循环条件，写成 while(a) 就会无限循环。题目最阴险的细节是 temp 变量完全隐形，只靠"先存后取"的顺序完成交换，不懂数据结构的学生极易漏写 temp。

🔄 反命题思维：若把循环条件改成 while(a)，因 a 始终非零，程序死循环；若去掉 temp，b 在 a=b 前已被覆盖，算法失效；若交换两句顺序，a 先拿余数，b 再拿旧 b，逻辑混乱。刷到类似题先问"变量交换用了什么结构"，这步不拆 temp 就掉坑。