枸杞加水

如何使用#

题目：求最大公因数 ((36,14)) 我们如何用辗转相除法做这道题呢？ 反复用除数除以余数直到除尽：

最后一个除数就是最大公约数，也就是 (2)。 我们算出最大公约数 ((36,14)=2)。 到这里，我们就知道如何使用辗转相除法了。 但是，鲁迅曾说过“我们学公式必须得懂得原理”，我们明白了原理才能灵活运用。

原理#

求最大公因数 ((a,b)) 首先我们推出这几条式子：

这是我们辗转法的原理

(a) 和 (b) 的最大公约数就等于 (b) 和 (r) 的最大公约数。 接下来让我们证明这条公式。

(1) 设 ((a,b)=d)，那么 (a=dm)，(b=dn)，然后我们将其带入 (r=a-bq)：

因为 (m,n,q) 都是整数，所以 (r) 是 (d) 的倍数，(d) 是 (r) 的因数。 所以：只要是 (a,b) 的因数，就一定是 (d,r) 的约数。

(2) 设 ((b,r)=d)，和之前一样，那么 (b=dx)，(r=dy)，然后将其代入 (a=bq+r)：

因为 (x,q,y) 都是整数，所以 (a) 是 (d) 的倍数，(d) 是 (a) 的因数。 所以：只要是 (d,r) 的因数，就一定是 (a) 的因数。 这样，我们就得出 ((a,b)) 的因数和 ((b,r)) 的因数相同，它们的因数都相同，那么它们的最大公因数也就相同。 所以我们要求 ((a,b)) 的最大公因数，我们就通过可以求 ((b,r)) 的最大公因数来得到。

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

题目：求最大公因数 ((36,14)) 反复用 ((a,b)=(b,r)) 的方法：

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

写 gcd 函数#

接下来看看我们如何在 C++ 中用辗转相除法写 gcd 函数。 gcd 函数就是用来求最大公因数的函数。

1
int gcd(int a, int b) {
2
    while (a % b != 0) // a能被b整除时就终止循环
3
    {
4
        int r = a % b;
5
        a = b;
6
        b = r; // 将a换成除数b，b换成余数r
7
    }
8
}

当然也可以直接用 algorithm 头文件中的 gcd 函数。 我们学会自己写是为了理解原理，提升思维， 自己写还可以在有特殊需求的时候更自定义化。