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

辗转相除法也被称为（ ）

辗转相除法（欧几里得算法）：gcd(a,b)=gcd(b,a%b)。当b=0时，gcd(a,0)=a。时间复杂度O(log min(a,b))。

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

【考点】数论｜算法｜最大公约数

1. 考纲定位 GESP五级数论模块核心考点，命题人卡住考生对算法名称的记忆盲区，绝大多数人知道“辗转相除”的操作却记不住标准命名。

2. 解题思维 看到“辗转相除法”先联想求最大公约数，再对照选项排除：高斯消元解线性方程、费马定理是数论定理、牛顿迭代求方程根，只有欧几里德算法专指辗转相除。

3. 陷阱拆解 选项A用“消元”混淆除法操作，选项B用“费马”借数论名头，选项D用“迭代”偷换算法流程，这些命名陷阱专盯死记硬背的考生，若只背操作步骤不懂算法归属必选错。

4. 反命题思维 若把题干改为“欧几里德算法用于求两个数的____？”，答案就是最大公约数；换成“牛顿迭代法与辗转相除法的核心区别”，答案指向前者求方程根、后者求最大公约数。记住：任何算法题先问“它到底算什么”，再对答案。