NOIP 普及 2013 第一轮 第 15 题：欧几里得算法计算最大公约数

题目

下面是根据欧几里得算法编写的函数，它所计算的是 $a$ 和 $b$ 的（	）。

int euclid(int a, int b)
{
if (b == 0)
return a;
else
return euclid(b, a % b);
}

选项

• A. 最大公共质因子
• B. 最小公共质因子
• C. 最大公约数
• D. 最小公倍数

答案

C

题解

考点定位

本题考「欧几里得算法」,对应大纲 2.1.3 初等数论（难度【2】）。

解题过程

euclid 辗转相除：gcd(a,b) = gcd(b, a mod b)，计算的是最大公约数。

选 C。

易错提醒

① 递归出口 b==0 返回 a；② 时间 O(log min(a,b))——斐波那契相邻项是最坏输入。