数论应用：拓展欧几里得与逆元求解同余方程

本资源是两个C++程序，分别用于解决数论问题，涉及同余方程和扩展欧几里得算法。 在数论中，同余方程是一类重要的数学问题，通常形式为 `ax ≡ b (mod m)`，其中 `a`、`b` 和 `m` 是整数，`x` 是我们要找的未知数。如果 `gcd(a, m) = 1`，那么方程有唯一解，可以通过扩展欧几里得算法求解。扩展欧几里得算法不仅求出最大公约数，还能同时计算出贝祖等式 `ax + my = gcd(a, b)` 的解。 在第一个程序中，题目的目标是找到一个逆元，即找到整数 `x` 使得 `ax ≡ 1 (mod m)`。这在模运算中非常常见，特别是在需要除法操作时。`inv()` 函数使用扩展欧几里得算法计算逆元。如果 `gcd(a, mod) != 1`，则不存在逆元，函数返回 `-1`。在主函数中，程序读取两个输入值 `a` 和 `b`，然后计算并输出 `a * inv(b, 9973) % 9973`，这是模9973下的乘法逆元。 第二个程序处理的是同余方程组，不强求模数两两互质，这里涉及到扩展中国剩余定理（Extended Chinese Remainder Theorem, ECRT）。题目要求解同余方程 `x ≡ x0 (mod m)` 和 `x ≡ y0 (mod n)`，其中 `m` 和 `n` 不一定互质。程序首先计算 `a = m - n`，`b = L`，`c = y - x`，然后利用扩展欧几里得算法求解。如果 `c` 与 `g = gcd(a, b)` 不同余，表示无解，输出 "Impossible"。否则，通过调整解 `x0` 使其满足模 `b` 的条件，最终输出解 `x0`。 这两个程序都使用了相同的扩展欧几里得算法实现，该算法的核心在于递归地解决较小的同余问题，直到基础情况 `b == 0`，此时 `a` 是 `b` 的最大公约数，而 `x` 和 `y` 分别对应贝祖等式的解。在递归过程中，不断更新 `x` 和 `y` 的值，直到回溯到基础情况。 这两个程序展示了如何使用C++和扩展欧几里得算法来解决数论中的同余问题，包括逆元的计算和非互质模数下的同余方程组。这些技巧在密码学、编码竞赛以及各种数学应用中都有广泛的应用。