Euclid 欧几里得算法

问题

求两正整数 $a$ 和 $b$ 的最大公约数（ $Greatest Common Divisor$ ）和最小公倍数（ $Least Common Multiple$ ）。

设 $gcd(a, b)$ 表示非负整数 $a, b$ 的最大公约数，任意正整数 $a$ 和 $b$ 满足：

gcd(a, b) = \begin{cases} b & a \bmod b = 0 \\ gcd(b, a \bmod b) & a \bmod b \neq 0 \end{cases}

也可以写作：

gcd(a, b) = \begin{cases} a & b = 0 \\ gcd(b, a \bmod b) & b \neq 0 \end{cases}

若 $a \lt b$ ，则第一步实际上会交换两个数字的位置，因为必然有 $a \div b = 0$ 。每一步得到的余数 $a \bmod b$ 都会越来越小，必然存在一个数字 $r$ 使得 $gcd(r, 0) = gcd(a, b)$ ， $r$ 即为 $a, b$ 的最大公约数。

设 $a_0, b_0$ 为原始的 $a, b$ ，用迭代式表达：

\begin{matrix} a_{0} = a, b_{0} = b \\ gcd(a_{0}, b_{0}) = gcd(b_{0}, a_{0} \bmod b_{0}) = gcd(a_{1}, b_{1}) & \rightarrow & a_{1} = b_{0}, b_{1} = a_{0} \bmod b_{0} \\ gcd(a_{1}, b_{1}) = gcd(b_{1}, a_{1} \bmod b_{1}) = gcd(a_{2}, b_{2}) & \rightarrow & a_{2} = b_{1}, b_{2} = a_{1} \bmod b_{1} \\ gcd(a_{2}, b_{2}) = gcd(b_{2}, a_{2} \bmod b_{2}) = gcd(a_{3}, b_{3}) & \rightarrow & a_{3} = b_{2}, b_{3} = a_{2} \bmod b_{2} \\ \cdots \\ gcd(a_{i}, b_{i}) = gcd(b_{i}, a_{i} \bmod b_{i}) = gcd(a_{i+1}, b_{i+1}) & \rightarrow & a_{i+1} = b_{i}, b_{i+1} = a_{i} \bmod b_{i} \\ \cdots \\ gcd(a_{n}, b_{n}) = gcd(b_{n}, a_{n} \bmod b_{n}) = gcd(a_{n+1}, 0) & \rightarrow & a_{n+1} = b_{n}, b_{n+1} = 0 \\ \end{matrix}

对于第 $k$ 步递归，有 $a_{k} = b_{k-1}, b_{k} = a_{k-1} \bmod b_{k-1}$ 。迭代到第 $n + 1$ 步时得到 $a_{n+1} = b_{n}, b_{n+1} = 0$ ， $a_{n+1}, b_{n}$ 即为最大公约数。

欧几里得算法的时间复杂度约为 $O(log_2 (max(a, b)))$ 。

Last updated 5 years ago