导读 提到数学中的经典算法，不得不提的就是欧几里得算法（又称辗转相除法）。它是一种用来计算两个整数最大公约数（GCD）的有效方法。简单来说...
提到数学中的经典算法，不得不提的就是欧几里得算法（又称辗转相除法）。它是一种用来计算两个整数最大公约数（GCD）的有效方法。简单来说，就是通过反复用较大数除以较小数，然后用余数替换较大的数，直到余数为零为止。此时剩下的非零数就是两者的最大公约数。
然而，除了基础的求解GCD功能，欧几里得算法还有更强大的扩展形式——扩展欧几里得算法。这项技术不仅能求出最大公约数，还能找到满足贝祖定理的一组整数解 `(x, y)`，使得 `ax + by = gcd(a, b)` 成立。这在密码学、线性代数等领域有着广泛应用。
💡举个例子：假设我们要求解 120 和 23 的最大公约数以及对应的系数。通过标准欧几里得算法，我们可以得到它们的最大公约数是 1；而使用扩展版本，则能进一步得出一组解 `(x=9, y=-47)`，验证了等式 `1209 + 23(-47) = 1`。
无论是基础还是扩展版本，欧几里得算法都堪称数学与计算机科学领域的璀璨明珠。🌟