ACM竞赛数论模板：欧几里德算法与扩展应用

"ACM数论模板包括欧几里德算法、中国剩余定理和欧拉函数等常用数论方法，常用于解决 ACM（国际大学生程序设计竞赛）中的数论问题。" 在ACM竞赛中，掌握一些基础的数论模板能够帮助参赛者快速解决涉及数论的问题。以下是对这些模板的详细解释： 1. **欧几里德算法**（Euclidean Algorithm）: 欧几里德算法用于计算两个整数的最大公约数（Greatest Common Divisor, GCD）。这里的实现是基于辗转相除法，通过不断用较大的数除以较小的数，并用余数替换较大数，直到余数为0。最终未被整除的数就是最大公约数。代码中的 `hcf` 函数实现了这个过程。 2. **最小公倍数**（Least Common Multiple, LCM）: 最小公倍数可以通过两个数的乘积除以它们的最大公约数来得到。在给定的代码中，`lcd` 函数接收两个整数 `u` 和 `v`，以及它们的最大公约数 `h`，返回 `u * v / h` 作为最小公倍数。 3. **扩展欧几里德算法**（Extended Euclidean Algorithm）: 扩展欧几里德算法不仅计算最大公约数，还能找到使得 `ax + by = gcd(a, b)` 成立的一组解 `(x, y)`。在 `ext_euclid` 函数中，它递归地处理了这个问题，返回了 `d`（即 `gcd(a, b)`），同时更新了 `x` 和 `y` 的值。这个算法对于解模线性方程 `ax ≡ b (mod n)` 非常有用。 4. **模线性方程的解法**: `modular_equation` 函数利用扩展欧几里德算法求解模线性方程 `ax ≡ b (mod n)`。如果 `c % d != 0`（其中 `d` 是 `gcd(a, b)`），则方程无解。否则，它可以找到最小正解 `x` 并输出所有正整数解。 5. **中国剩余定理** (Chinese Remainder Theorem, CRT): 中国剩余定理是解决一组同余方程 `x ≡ a_i (mod m_i)` 的经典工具，其中 `a_i` 和 `m_i` 分别是每个方程的余数和模数。在ACM中，通常简化为解决二元同余方程组。`ext_euclid` 函数可以用来求解单个模线性方程，但解决更复杂的中国剩余定理问题通常需要更高级的方法，如Yao's algorithm或Kasami-Welch算法。 在ACM比赛中，了解并熟练应用这些数论模板是至关重要的，因为它们可以帮助参赛者高效地解决各种数论问题，从而提高解决方案的正确性和速度。