算法笔记 -- 辗转相除法

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

整除

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

$b÷a=q...r$，其中$0\le r<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,amodb)$

证明步骤如下所示：

首先我们不妨假设$a>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=amodb$，故$gcd(a,b)=gcd(b,amodb)$。

附上cpp代码实现

CPP 复制

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