算法笔记 -- 辗转相除法

今天突然看到一题有关\(gcd\)求最大公约数的算法，竟然用暴力没法求出来，就来复习一下\(gcd\)算法了🤣。

整除

首先我们要职的gcd是干什么的，gcd一般是用在求两个整数的最大公约数，而说到约数又要先提到除法，对于整数中的除法，我们一般有如下通用表示形式：

\(b \div a = q...r\)，其中\(0\le r \lt a\)，\(b,\ a,\ q,\ r \in N\)。

若\(r=0\)，则称\(b\)能够被\(a\)整除或称\(a\)能够整除\(b\)，记作\(a\ |\ b\)，否则说明不能被\(a\)整除。

其中整除具有传递性：

若\(a\ |\ b\)，\(b\ |\ c\)，则\(a\ |\ c\)

组合性：

若\(a\ |\ b\)，\(a\ |\ c\)，对于任意\(m,n \in K\)，都有\(a\ | \ (mb + nc)\)。

欧几里得算法

稍微了解了整除的定义后，我们来看\(gcd\)算法中著名的欧几里得算法：

\(gcd(a,\ b) = gcd(b,\ a\ mod\ b)\)

证明步骤如下所示：

首先我们不妨假设\(a \gt b\)，则\(a = b \times q + r\) ①

又因为此时\(a\)与\(b\)有公约数，\(u\ |\ a\)，\(u\ |\ b\)。不妨设公约数为\(u\)，则\(a=x\times u\)，\(b=y\times u\)。由①可得\(r=xu-yuq=u(x-yq)\)。又因为\(u,\ x,\ y \in K\)，故\(x-yq \in K\)。设\(z=x-yq\)，故\(r=z\times u\)，\(u\ |\ r\)。

又因为\(r=a\ mod\ b\)，故\(gcd(a,\ b) = gcd(b,\ a\ mod\ b)\)。

附上cpp代码实现

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