ACM数论模板：扩展欧几里德与不定方程解法

"本文档提供了一份关于ACM竞赛中常用的数论模板，包括扩展的欧几里德算法、不定方程的解法、中国同余定理以及与原根、积性函数、欧拉函数相关的知识点。这些内容对于理解和解决数论问题非常有帮助。" 扩展的欧几里德算法和不定方程的解： 扩展的欧几里德算法是用来求解两个整数的最大公约数（GCD）的同时，找到一组贝祖等式ax + by = gcd(a, b)的解。在解决不定方程ax + by = n的问题时，首先需要计算a和b的最大公约数。如果gcd(a, b)不能整除n，那么方程没有整数解。否则，可以将方程转换为gcd(a, b)的倍数形式，即a'x + b'y = n'，其中gcd(a', b') = 1。然后，找到方程a'x + b'y = 1的一个整数解(x0, y0)，所有解可以通过x = n'/gcd * x0 + b'/gcd * t和y = n'/gcd * y0 - a'/gcd * t来表示，t为任意整数。 中国同余定理： 中国同余定理是数论中的一个重要工具，用于解决同余方程组的问题。它表明，如果给定一系列模数m_i和对应的余数r_i，且它们满足模线性同余方程组，即x ≡ r_i (mod m_i)，那么存在一个解x，且这个解是模m_1 * m_2 * ... * m_k的唯一同余类。在程序实现中，通常通过扩展的欧几里德算法来寻找解。 原根和积性函数： 原根是指在模p意义下，具有指数性质g^k ≡ 1 (mod p)的最小正整数k，称为g的阶。积性函数是这样的函数f：N → Z，对于所有的正整数m和n，如果(m, n) = 1，则f(mn) = f(m) * f(n)。原根和积性函数在密码学和编码理论中有广泛应用。 欧拉函数性质： 欧拉函数φ(n)定义为小于n且与n互质的正整数的数量。欧拉函数有若干重要的性质，例如φ(p^k) = p^(k-1) * (p-1)，其中p是素数。此外，欧拉函数还满足φ(ab) = φ(a) * φ(b)，当a和b互质时。在编程竞赛中，快速计算欧拉函数的值是必要的。 线性求1-max的欧拉函数值： 在线性时间内求出1到max之间所有数的欧拉函数值之和，可以利用欧拉函数的性质和预处理数据来实现。这在处理涉及欧拉函数的复杂问题时非常有用。 求单个欧拉函数，求最小的x满足phi（n）%x == 0： 这个问题要求找到最小的x，使得2^x对模n取模等于1。这可以通过计算n的循环节长度（也称为欧拉序）来解决，该长度与欧拉函数有关。可以使用扩展欧几里德算法和原根的概念来找到这个最小的x。 总结： 这些模板提供了ACM竞赛中数论问题的基本工具，包括求解不定方程、应用中国同余定理、理解和计算原根、积性函数和欧拉函数。掌握这些知识对于提高在算法竞赛中的表现至关重要。