ACM竞赛数论模板：扩展欧几里德与同余定理

"这篇资源主要介绍了数论在ACM竞赛中的应用，提供了数论的一些基本模板，包括扩展的欧几里德算法、中国同余定理以及与原根、积性函数、欧拉函数相关的知识。" 在ACM竞赛中，数论是一个重要的理论基础，用于解决各种复杂的问题。以下是对资源中提及的数论知识点的详细解释： 1. **扩展的欧几里德算法**：这是一个用于求解最大公约数(greatest common divisor, GCD)的算法，并且可以找到一组整数解使得`ax + by = gcd(a, b)`。在资源中给出了C++实现，该算法递归地计算两个数的最大公约数，并同时返回满足条件的x和y。 2. **不定方程的解**：利用扩展的欧几里德算法，可以求解不定方程`ax + by = n`的整数解。如果`gcd(a, b)`能整除`n`，那么存在解；否则无解。解的形式为`x = n/gcd * x0 + b/gcd * t`和`y = n/gcd * y0 - a/gcd * t`，其中`(x0, y0)`是`a'x + b'y = 1`的一组解，`t`是整数。 3. **中国同余定理**：也称为中国剩余定理（Chinese Remainder Theorem, CRT），在数论中，它提供了解一组同余方程的系统方法。在资源中，给出了一个简单的示例实现，但完整的中国同余定理处理的是多个同余方程，如`x ≡ a1 (mod m1)`, `x ≡ a2 (mod m2)`, ..., `x ≡ an (mod mn)`，并能找到唯一解（模乘积`m1 * m2 * ... * mn`的模意义下）。 4. **原根**：在模p的意义下，如果一个数g对于模p的每一个非零剩余类都有幂次为1的倍数，那么g被称为模p的原根。原根在密码学和编码理论中有重要应用，比如计算离散对数。 5. **积性函数**：积性函数是一类特殊的数论函数，其定义为，如果f是积性函数，对于任意正整数a和b互质，有f(ab) = f(a) * f(b)。欧拉函数φ(n)是一个典型的积性函数，表示小于等于n且与n互质的正整数的数量。 6. **欧拉函数性质**：欧拉函数φ(n)有多种性质，例如φ(p^n) = p^n - p^(n-1)对于素数p的幂次，φ(mn) = φ(m) * φ(n)如果m和n互质。欧拉函数在计算模运算中的指数幂、判断素性、以及计算群的阶等方面有重要作用。 7. **线性求1-max的欧拉函数值**：在一些问题中，我们需要快速计算从1到某个数n之间所有数的欧拉函数值的和，这可以通过动态规划或者前缀和优化来高效求解。 8. **求单个欧拉函数**：给定一个数n，要求找到最小的x使得`2^x ≡ 1 (mod n)`，这涉及到模运算中的指数循环节和欧拉定理。 9. **求最小的x满足phi(n) % x == 0**：这通常与模逆元有关，可以通过扩展欧几里德算法找到模n下的逆元。 这个资源提供了ACM竞赛中数论问题的基础模板和解决方案，对于参赛者来说是宝贵的参考资料。通过理解和掌握这些内容，可以有效地解决涉及数论的问题，提高算法竞赛的表现。