Oct 22, 2017

欧几里得算法

天杀的，原来我现在都蠢到连最大公约数的求解算法理解都这么费劲，欧几里得算法又称辗转相除法，用于计算两个数的最大公约数。

简介

多应用领域在计算机和数学两个领域，计算公式为：

$$ gcd(a, b) = gcd(b, mod(a, b)), a > b且a和b为正整数 $$

古希腊数学家欧几里德在其著作《The Elements》中最早描述了这种算法, 所以被命名为欧几里德算法。算法依赖于下面的定理：

两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。

证明

两种证明定理的思路。

若整数 $d$ 整除整数 $a$ ，记作 $d\vert a$。

方法1

设:

$$ \begin{aligned} & r = \ a\ \boldsymbol{\mathrm{mod}}\ b, 有r = a - kb\\
& d 是 a和b 的公约数, 记: d \vert a, d \vert b \end{aligned} $$

那么，

$$ \begin{aligned} & r = a - kb, 等式两边同时除以d \Longrightarrow \frac{r}{d}=\frac{a}{d}-\frac{kb}{d}\\
& \because d \vert a且 d \vert b\\
& \therefore d \vert r \end{aligned} $$

所以，$d$ 也是 $b$ 和 $a\ \boldsymbol{\mathrm{mod}}\ b$ 的公约数。

设:

$$ \begin{aligned} & r = \ a\ \boldsymbol{\mathrm{mod}}\ b, 有r = a - kb\\
& d 是 a和a\ \boldsymbol{\mathrm{mod}}\ b的公约数, 记: d \vert a, d \vert (a-kb) \end{aligned} $$

那么，

$$ d \vert a即，d也是a的约数 $$

综上，$a$ 和 $b$ 的公约数与b和 $a\ \boldsymbol{\mathrm{mod}}\ b$ 的公约数是一致的，那么最大公约数也是一样。

方法2

令:

$$ c = gcd(a, b) \xrightarrow[]{m,n为整数} \begin{cases}a=mc\\b=nc\end{cases} $$

有,

$$ \begin{aligned} r&=a-kb\\
&=mc-knc\\
&=(m-kn)c \end{aligned} $$

$(m-kn)$ 为整数，那么有c整除余数r，即:

$$ c \vert r $$

下面证明 $c = gcd(b, r)$:

设$m-kn$ 和 $n$ 有大于1的公约数$d$，即

$$ \begin{cases}m-kn&=xd\\n&=yd\end{cases} \Longrightarrow \begin{aligned}m&=kn+xd\\&=kyd+xd\\&=(ky+x)d\end{aligned} $$

$$ \therefore \begin{cases} a&=mc=(ky+x)cd\\
b&=nc=ycd \end{cases} $$

那么有$cd \vert a 且 cd \vert b$，这与$c$ 是 $a$ 和 $b$ 的最大公约数是矛盾的。也就是说不存在 $d>1$ 满足上述过程，也就是说有：

$$ c=gcd(b, r) $$

综上可得：

$$ c=gcd(a, b)=gcd(b, r) $$

实现思路

实现思路就是，不断的取模求最大公约数，直到整除为止就能得到最终要求解最大公约数。

  1. 令 $r = a\ \boldsymbol{\mathrm{mod}}\ b, (0 \le r < b )$ 若 $r=0$ 算法结束, $b$ 就是最终结果

  2. 算法过程: $a \leftarrow b, b \leftarrow r$，返回步骤1

具体实现

c版本

int gcd(int a, int b)
{
    int r;
    while(b > 0)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

c++版本

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

python版本

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