ACM竞赛数论攻略：扩展欧几里德、中国同余定理与欧拉函数

"这篇文档是关于ACM竞赛中常用的数论模板，主要涵盖扩展的欧几里德算法、不定方程的解法、中国同余定理、原根概念、积性函数、欧拉函数的性质以及如何求解特定的欧拉函数值问题。文档以C语言的形式给出了实现这些理论的代码示例。" 在数论中，这些知识点对于解决复杂计算问题至关重要： 1. **扩展的欧几里德算法**：这是一个用于计算最大公约数（GCD）并找出整数线性同余方程解的算法。通过递归地应用基本的欧几里德算法，可以找到使得`ax + by = gcd(a, b)`的整数解`x`和`y`。代码中`extend_Euclid`函数实现了这一过程。 2. **不定方程的解**：不定方程`ax + by = n`的解可以通过扩展欧几里德算法找到。如果`gcd(a, b)`能整除`n`，则存在解，否则无解。一旦找到`a'x + b'y = 1`的解，就可以构造出原方程的解。 3. **中国同余定理**：这是数论中的一个重要定理，它允许我们解一组同余方程，如`x ≡ a1 (mod m1), x ≡ a2 (mod m2), ..., x ≡ an (mod mn)`，当模数两两互质时。`Poj2891`代码可能是一个使用中国同余定理解题的示例。 4. **原根**：在模p下，如果一个数g能生成模p所有非零剩余类的乘法群，那么g就是一个原根。原根在密码学和编码理论中有重要应用。 5. **积性函数**：积性函数是这样一个函数，如果两个正整数没有公因数，那么该函数的值等于这两个数的函数值之积。欧拉函数`φ(n)`就是典型的积性函数。 6. **欧拉函数性质**：欧拉函数`φ(n)`表示小于n且与n互质的正整数的数量。欧拉函数在数论中有很多有趣的性质，例如`φ(p^k) = p^k - p^(k-1)`，其中p是素数。 7. **线性求1-max的欧拉函数值**：在某些问题中，我们需要快速求出`1, 2, ..., max`的欧拉函数值的线性组合，这在数论算法中是非常常见的一类问题。 8. **求单个欧拉函数的特殊解**：寻找最小的x，使得`φ(n) % x == 0`，同时满足`2^x ≡ 1 (mod n)`。这类问题通常涉及到模运算和数论的性质。 这些模板和方法是ACM竞赛选手必备的工具，它们可以帮助选手快速高效地解决复杂的数学和算法问题。掌握这些知识点不仅可以提升在竞赛中的表现，也是深入理解和应用数论的基础。