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

辗转相除法用于求两个整数的最大公约数。

辗转相除法求最大公约数：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 五级算法模块的“经典算法”考点，命题人用“辗转相除法用于求最大公约数”这句话卡住的是对算法名称和用途的机械记忆——很多考生只背“欧几里得算法求最大公约数”，却混淆了“辗转相除”和“欧几里得除法”的表述差异。

2. 🧠 解题思维（拆解与通法） 看到“辗转相除”先联想除法的递归结构，关键观察是余数序列必然递减直至 0，因此用递归或循环实现：while(b) { t=a%b; a=b; b=t; } 最后 a 即为最大公约数。这一类“求公约数/公倍数”的题通法就是利用数论中的整除性质构造递推。

3. 🪤 陷阱拆解（命题人的套路） 错误选项往往把算法描述成“先求商再求余”或“只用一次除法”，命题人利用考生对算法流程的模糊记忆；最阴险的细节是“两个整数”未限定正负，但辗转相除法对任意非零整数依然成立，所以题干表述完全正确。

4. 🔄 反命题思维（教练升华） 如果把“用于求”改成“只能用于求”，答案就变错；若把“辗转相除”换成“更相减损术”，通法不变但实现细节不同。刷到类似题先问“命题人想考我什么”——是考名称、考流程还是考适用条件。