辗转相除法.docx

辗转相除法
辗转相除法是一种古老且非常有效的求两个数的最大公约数的方法，也叫欧几里得算法(Euclidean algorithm)。这种算法可以很简单和快速的求解最大公约数。在这篇文章中，我们将会详细介绍辗转相除法，并提供一些例子来说明如何使用它来解决问题。

辗转相除法的基本思想是: 用较小的数去除较大的数，再用余数去除较小的数，如此反复，直到余数为零为止。此时，除数就是原两个数的最大公约数。例如: 求30和45的最大公约数，我们可以按照下面的步骤进行计算:

① 用 45 去除 30，余数为 15;
② 用 30 去除 15，余数为 0;
③ 因为余数为 0，所以最大公约数为 15。

下面我们就来详细介绍一下辗转相除法的具体步骤:

步骤 1: 将两个数 a 和 b 相除 (a > b)，并求出余数 r1。

$a = bq_1 + r_1$

步骤 2: 将 b 和 r1 相除，并求出余数 r2。

$b = r_1q_2 + r_2$

步骤 3: 将 r1 和 r2 相除，并求出余数 r3。

$r_1 = r_2q_3 + r_3$

步骤 4: 如此反复，直到余数为 0 为止。此时，除数就是原两个数的最大公约数。

$r_{n-2} = r_{n-1}q_n + 0$

最后将最后一个不为零的余数即为所求的最大公约数。

这个过程可以用图示来表示如下:

![辗转相除法示意图](https://img-

接下来，我们通过一些例子来进一步了解如何使用辗转相除法来解决问题。

例1: 求 252 和 105 的最大公约数。

样例输入:

252

105

样例输出:

21

解题思路:

将较大的数(252)除以较小的数(105),得到余数47。

再将105除以47,得到余数11。

再将47除以11,得到余数3。

再将11除以3,得到余数2。

最后，将3除以2，得到余数1。因为余数为1，所以最大公约数为1。

答案是21的原因: 最大公约数为1，252和105同时被1整除，所以252和105的公因数只有1。

Python代码如下:

def gcd(a, b):
while b != 0:
a, b = b, a % b
return a

a, b = int(input()), int(input())
print(gcd(a, b))

例2: 求 340 和 136 的最大公约数。

样例输入:

340

136

样例输出:

4

解题思路:

将较大的数(340)除以较小的数(136),得到余数68。

再将136除以68,得到余数0。

最后，将较小的数即为所求的最大公约数，因为 340 = 4 × 85, 136 = 4 × 34，所以最大公约数为 4。

答案是4的原因: 340和136都能够被4整除，故而最大公因数为4。

Python代码如下:

def gcd(a, b):
while b != 0:
a, b = b, a % b
return a

a, b = int(input()), int(input())
print(gcd(a, b))

总结:

辗转相除法是一种非常简单和有效的方法，可以用来求两个数的最大公约数，可以使用循环或递归进行实现。其实质是利用辗转相除，不断地将被除数和除数进行整除和求余，直到找到最大公约数，运算次数是比较少的。在对数据量比较大的数求最大公约数时特别方便，一般用在暴力枚举、线性筛法、高斯消元法等算法中。