使用递归实现欧几里得算法计算最大公约数

"欧几里得算法用于计算两个正整数的最大公约数，通过递归实现。当m除以n的余数为0时，最大公约数即为n；否则，最大公约数为gcd(n, m%n)。程序采用C语言编写，并处理了负数输入的情况。" 在计算机科学中，欧几里得算法（Euclidean Algorithm）是一种古老而高效的算法，用于计算两个正整数的最大公约数（Greatest Common Divisor, GCD）。该算法基于以下原理：两个正整数m和n（m > n）的最大公约数等于n和m除以n的余数的最大公约数。用数学公式表示就是： gcd(m, n) = gcd(n, m % n) 如果n为0，则m是最大公约数，因为任何非零整数除以0都无定义。这个算法可以递归地应用，直到余数变为0，从而找到最大公约数。 在提供的C语言代码中，函数`extend_gcd(int m, int n, int x, int y)`实现了扩展欧几里得算法，它不仅返回最大公约数，还返回一组x和y，使得ax + by = gcd(m, n)，这是线性同余方程的一种解。这里的x和y对应于贝祖等式的系数。在代码中，负数被转换为正数以保持算法的正确性。函数使用了递归，每次调用将问题规模减小，直到n为0，此时返回m作为最大公约数，并计算出x和y的值。 主函数`int main()`读取用户输入的两个数m和n，然后调用`extend_gcd`函数并打印结果。输入处理部分使用了`~scanf("%d%d", &m, &n)`来读取整数，其中`~`操作符用于确保循环条件始终为真，直到输入结束。 样例输入和输出展示了不同情况下的最大公约数计算，包括正数、负数和一个为0的输入。所有测试用例的结果均正确，显示了算法的正确性和鲁棒性。 扩展欧几里得算法在许多领域都有应用，如数论、密码学（例如RSA公钥加密算法）以及求解线性同余方程等。理解并能够实现这个算法对于学习和工作在与数论和计算理论相关的IT领域的人来说是至关重要的。