辗转相除法是一种求最大公因数的计算方法。

这种方法在编程中很常用，在数学计算中也可以用来求很复杂的最大公因数问题。

如何使用

题目：求最大公因数(36,14)

我们如何用辗转相除法做这道题呢？ $$ \displaylines{ 反复用除数除以余数直到除尽\ 36{\div}14=2\dots8\ 14{\div}8=1\dots6\ 8{\div}6=1\dots2\ 6{\div}2=3\ 最后一个除数就是最大公约数，也就是2 } $$ 我们算出最大公约数(36,14)=2

到这里，我们就知道如何使用辗转相除法了。

但是，鲁迅曾说过“我们学公式必须得懂得原理”，我们明白了原理才能灵活运用

原理

求最大公因数(a,b)

首先我们推出这几条式子 $$ \displaylines{ a{\div}b=q\dots r \ a=bq+r \ r=a-bq } $$ 这是我们辗转法的原理 $$ \displaylines{ (a,b)=(b,r) \a和b的最大公约数就等于b和r的最大公约数 } $$ 接下来让我们证明这条公式 $$ \displaylines{ (1)设(a,b)=d\ 那么a=dm,b=dn\ 然后我们将其带入r=a-bq\ 得r=d(m-nq)\ 因为m,n,q都是整数，所以r是d的倍数，d是r的因数\ 所以：只要是a,b的因数，就一定是d,r的约数\ } $$

$$ \displaylines{ (2)设(b,r)=d\ 和之前一样，那么b=dx,r=dy\ 然后将其代入a=bq+r\ 得a=d(xq+y)\ 因为x,q,y都是整数，所以a是d的倍数，d是a的因数\ 所以：只要是d,r的因数，就一定是a的因数\ } $$

这样，我们就得出(a,b)的因数和(b,r)的因数相同，它们的因数都相同，那么它们的最大公因数也就相同。

所以我们要求(a,b)的最大公因数，我们就通过可以求(b,r)的最大公因数来得到。

现在我们再来看看开头的题

题目：求最大公因数(36,14)

反复用(a,b)=(b,r)的方法

(36,14)=(14,8)=(8,6)=(6,2)

最后得到(6,2)，显而易见最大公约数是2

写gcd函数

接下来看看我们如何在C++中用辗转相除法写gcd函数

gcd函数就是用来求最大公因数的函数

1
2
3
4
5
6
7

int gcd(int a,int b) {
	while (a % b != 0) //a能被b整除时就终止循环
    {
		int r = a % b;
		a = b;
		b = r; //讲a换成除数b，b换成余数r
	}

当然也可以直接用algorithm头文件中的gcd函数，

我们学会自己写是为了理解原理，提升思维，

自己写还可以在有特殊需求的时候更自定义化。