NOIP 普及组初赛 · NOIP 2013 普及组初赛试题 第 15 题

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

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

看到递归和取模运算，马上联想到欧几里得算法（辗转相除法）。这道题就是让你识别代码在求什么，直接抓住'递归终止条件b==0时返回a'这个核心特征，就能锁定答案。

很多同学容易把欧几里得算法和最小公倍数搞混，觉得都是求'共同'的东西。其实最小公倍数是L=a*b/GCD(a,b)，代码里完全没有乘法求积的步骤，也没有最后除以GCD的操作。另外，有人可能误以为是求最大公共质因子，比如a=12,b=18，最大公共质因子是2，但GCD是6，显然代码求的是6而不是2。记住：辗转相除求的是两个数的最大公约数，不是质因子，也不是最小公倍数。

欧几里得算法：一道经典的递归题

考点与概念

这道题考查的是欧几里得算法，也叫辗转相除法，用来求两个整数的最大公约数（GCD）。

什么是最大公约数？就是能同时整除两个数的最大正整数。比如12和18，公约数有1、2、3、6，其中最大的是6，所以GCD(12,18)=6。

欧几里得算法的核心思想非常巧妙：两个数的最大公约数，等于其中较小的数和两数相除余数的最大公约数。用公式表示就是：

$$\text{gcd}(a, b) = \text{gcd}(b, a \bmod b)$$

这个性质看起来很玄，但其实很好理解：任何能整除a和b的数，必然也能整除a除以b的余数。反过来，能整除b和余数的数，也一定能整除a。所以两者的公约数集合完全一样，最大的那个自然也不变。