数论在计算机科学，尤其是算法竞赛（如ACM）中占据着重要的地位，因为它能解决很多复杂的计算问题。本文将详细解析ACM中常用的数论模版，包括欧几里得算法、扩展欧几里得算法以及中国剩余定理。
1. **欧几里得算法**：用于计算两个整数的最大公约数（Greatest Common Divisor, GCD）。在给出的代码中，`hcf`函数实现了基本的欧几里得算法，通过不断取余直到其中一个数为零，然后返回另一个非零数作为GCD。`lcd`函数则根据两个数的GCD计算它们的最小公倍数（Least Common Multiple, LCM）。
2. **扩展欧几里得算法**：这是欧几里得算法的扩展，除了返回GCD外，还能同时求出两个整数a和b的线性组合ax + by = GCD(a, b)的一组解x和y。在代码中，`ext_euclid`函数实现了这一算法。它递归地处理b和a%b，直到b为零，然后回溯计算x和y。`modular_equation`函数利用扩展欧几里得算法解决同余方程ax ≡ b (mod n)，当c % GCD(a, b) ≠ 0时，方程无解，否则可以找到所有解。
3. **中国剩余定理**：在数论中，中国剩余定理（Chinese Remainder Theorem, CRT）解决了多个同余方程组的问题。在给出的`China`函数中，它接受一个整数数组W（代表模数）和B（代表剩余数），以及模数的个数k，然后计算满足一系列同余关系的x：x ≡ Bi (mod Wi)，i = 1, 2, ..., k。函数计算所有模数的乘积n，然后通过扩展欧几里得算法找出每个模数Wi和它们的最小公倍数m的线性组合，最后结合所有结果得到x的值。
这些模版在实际编程竞赛中非常实用，例如在处理数论问题、加密算法、素数检测和分解质因数等方面。理解并熟练掌握这些模版可以帮助ACM竞赛选手在有限的时间内快速解决问题。通过不断的练习和应用，可以提高在算法竞赛中的表现。
