什么是欧几里得算法？
欧几里得算法是人类已知最古老的算法之一，由古希腊数学家欧几里得在约公元前 300 年提出，在中国也常被称为"辗转相除法"。它能高效地求出两个整数的最大公约数（GCD），也就是能同时整除这两个数且没有余数的最大整数。本计算器还会顺带给出最小公倍数（LCM），它可以直接由最大公约数推算出来。
如何使用本计算器
在上方两个输入框中分别填入两个整数，然后提交即可。计算器会取输入值的绝对值，反复套用公式 \(\gcd(a, b) = \gcd(b, a \bmod b)\)，直到余数变为零为止，随后同时给出最大公约数和最小公倍数。
公式详解
核心原理是：用较大的数除以较小的数，再用所得余数替换较大的数，两个数的最大公约数始终保持不变。用符号表示就是 $$\gcd(a, b) = \gcd(b, a \bmod b)$$ 不断重复这一过程，直到 \(b = 0\) 时停止，此时最后一个非零的数就是最大公约数。最小公倍数则由 \(\operatorname{lcm}(a, b) = \dfrac{a \times b}{\gcd(a, b)}\) 求得——因为两个数的乘积恰好等于它们最大公约数与最小公倍数的乘积。
实例演算
求 \(\gcd(48, 36)\)：\(48 \bmod 36 = 12\)，于是转为求 \(\gcd(36, 12)\)；接着 \(36 \bmod 12 = 0\)，因此最大公约数为 12。再算最小公倍数：$$\frac{48 \times 36}{12} = \frac{1728}{12} = 144$$
常见问题
如果其中一个数是零怎么办？ \(\gcd(a, 0) = a\)。算法会自然处理这种情况——循环立即停止，并返回那个非零的数。
a 和 b 的先后顺序重要吗？ 不重要。\(\gcd(a, b) = \gcd(b, a)\)；算法在第一步就会自动调整顺序。
可以输入负数吗？ 可以。计算器会取绝对值，因为按照惯例，最大公约数定义为正数。
