GESP 六级 · GESP 202403 C++ 六级 第 14 题

以下代码使用了辗转相除法求解最大公因数，请在横线处填入（ ），使其能正确实现相应功能。

int gcd(int a, int b) {
    while (b != 0) {
        ________________________
    }
    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的顺序不影响结果。

【考点】递归/辗转相除法｜取模运算｜变量交换

1. 🎯 考纲定位

GESP 六级 C++ 要求掌握递归算法与经典数学算法，辗转相除法属于"常用算法"模块的核心内容。命题人把这道题放在六级，不是为了考你背不背过欧几里得，而是卡住那些只会套模板、不懂算法原理的考生——他们看到 gcd 就条件反射写 a%b，却忘了变量更新顺序，结果整个逻辑全错。