求最大公约数

这是一个非常基础也非常容易想不起来的算法，我在大一的时候曾经多次和类似的入门算法打交道，但是到了今天突然要用的时候还是特别容易忘，没有办法一下子有思路。

因为总是希望产出更好的东西，所以所学的鸡毛蒜皮不敢直接写出来，所以一拖再拖，总是违背了自己的初心。所以今天有想法的时候，不敢拖延，急忙动笔。

辗转相除法求最大公约数

求最大公约数的时候，稍有基础的人都会一下子想到辗转相除法，但辗转相除法是什么呢，又怎么去证明辗转相除法的合理性呢。我会在这篇文章中尽可能详细地解释并且找到一个好联想回忆的记忆方法。

文字描述

用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

伪码描述

Euclid(m,n)  
输入：非负整数 m, n，其中m与n不全为0,  
输出：m 与 n 的最大公约数
1. while m>0 do
2. r <- n mod m
3. n <- m
4. m <- r
5. return n

动图例子

这里展示了一个求最大公约数的方法，求36和27的最大公约数。

原理解释

我们可以用一个比较直观的方法去记忆这个算法。

首先，当我们要求两个数的最大公约数时，这个最大公约数要尽可能大，最大的情况就是等于两个数中较小的那一个。

假设要求 $ a $ 和 $ b $ 的最大公约数，且已知 $ a<b $ .

我们先验证较小的数 $ a $ 是否为最大公约数，已知 $ a $ 一定为本身的约数，那么我们要做的就是看看他是不是 $ b $ 的约数，我们用 $ a $ 去除 $ b $ .

余数为零，我们则可以判定最大公约数即为 $ a $ .

余数不为零，则说明 $ a $ 不能整除 $ b $ ，可以得知 $ a $ 不是两个数的最大公约数，这样，我们应该继续往下去找最大公约数，因为 $ b $ 不能被 $ a $ 整除，会有一个余数，这个时候我们可以把b分成两部分，一部分是 $ b/a $ 的商（我们把它记为 $ c $ ）和 $ a $ 的乘积 $ a/c $ ，还有一部分就是余数（我们把它记为 $ d $ ）。

显然 $ a $ 是 $ a*c $ 的约数，所以 $ a $ 和 $ d $ 的最大公约数 $ e $ ，也一定是 $ a*c $ 的约数，倘若我们能求出 $ a $ 和 $ d $ 的最大公约数 $ e $ ，那么它就是$ a $ ， $ d $ 和 $ a*c $ 的最大公约数。

因为 $ b=a*c+d $ ， $ e $ 也是 $ a $ 和 $ b $ 的最大公约数。

如此递归相除直至余数为零，这就是辗转相除法。

C++代码

int gcd(int a,int b){
  return b?gcd(b,a%b):a;
}