GESP 五级 · GESP 202509 C++ 五级 第 5 题

以下代码计算两个正整数的最大公约数 (GCD)，横线上应填写（ ）。

int gcd0(int a, int b) {
    if (a < b) {
        swap(a, b);
    }
    while(b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return ______;
}

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

区分排列（考虑顺序，$P(n,m)$）和组合（不考虑顺序，$C(n,m)$）。注意特殊元素优先处理、正难则反等计数技巧。

【考点】欧几里得算法｜变量追踪

1. 🎯 考纲定位：GESP五级算法模块核心考点。命题人专门卡住"循环终止后变量状态追踪"这一高频薄弱点——多数考生只记得算法流程，却忽略while循环结束时b必为0、a才是最终GCD这一关键状态。

2. 🧠 解题思维：看到辗转相除代码要立即识别欧几里得算法框架。关键观察是每次迭代a,b都按余数规则更新，循环条件b!=0保证最终b归零；此时a保存的正是两数最大公约数。因此横线必须填a，这是算法正确性的直接体现。

3. 🪤 陷阱拆解：选项A填b是最典型错误——命题人利用"循环条件b!=0"制造干扰，诱导考生误以为b是结果；选项C填temp则混淆了中间变量与返回值的关系；选项D填a*b更是偷换概念，把GCD与最小公倍数(LCM)的乘积关系混为一谈。最阴险的细节在于"绝对化表述"：循环必然以b=0结束，但返回b则永远为0，这违背GCD定义。

4. 🔄 反命题思维：若将while条件改为a!=b，算法仍正确但终止时a=b=GCD，此时填a或b皆可；若改为递归写法，返回值应填gcd(b,a%b)而非a。刷到类似题先问："循环结束后哪个变量保存了目标值？"——这是所有辗转相除、取模循环题的通用判据。