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

下列 C++ 代码用两种方式求解两个正整数的最大公约数，说法错误的是（ ）。

int gcd0(int big, int small) {
    if (big < small) {
        swap(big, small);
    }
    if (big % small == 0) {
        return small;
    }
    return gcd0(small, big % small);
}

int gcd1(int big, int small) {
    if (big < small) {
        swap(big, small);
    }
    for (int i = small; i >= 1; --i) {
        if (big % i == 0 && small % i == 0)
            return i;
    }
    return 1;
}

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

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】GCD算法｜时间复杂度｜循环条件

命题人把"算法效率对比"和"循环边界"两个高频考点揉进同一道题，就是要卡住只会背模板、不看代码细节的考生。

逐项拆解： A. gcd0 是典型的欧几里得算法，每次递归把问题规模至少减半（取模后余数小于除数），理论时间复杂度为 $O(\log n)$，正确。 B. gcd1 从 small 向下枚举到 1，最坏循环次数与 small 成正比，即 $O(n)$，正确。 C. 对数级复杂度天然优于线性级，故 gcd0 效率更高，正确。 D. 原循环 i >= 1 会检查 i = 1 并返回 1，这是必要的；改成 i > 1 后，循环在 i = 1 处直接终止，但函数末尾仍会执行 return 1;，逻辑完全等价。因此"应该修改"是错误表述，D 为本题答案。

命题人最阴险的陷阱在于 D 选项：很多人以为"循环到 1 多一次判断"是多余的，却忽略了当 small = 1 时，i >= 1 会进入循环体立即返回 1，而 i > 1 会跳过循环体直接进入 return 1;，结果一样。只背结论不看执行流程，就会掉进这个陷阱。

反命题思维：如果把 gcd1 改成 for (int i = small; i >= 2; --i) 并删除最后的 return 1;，这道题答案就会变成"说法错误的是 C"，因为那时 gcd1 将无法正确返回 1。刷到类似题时，先问自己"循环边界到底改了哪一步，返回值是否受影响"。