数论模板：扩展欧几里德与同余定理解析

"这篇资源主要涉及数论中的模板，涵盖了扩展的欧几里德算法、中国同余定理以及相关的不定方程解法。" 在数论领域，扩展的欧几里德算法（Extended Euclidean Algorithm）是解决模线性同余方程的基础。这个算法不仅用于计算最大公约数（GCD），还能找到满足ax + by = gcd(a, b)的整数解x0和y0。在解不定方程ax + by = n时，如果gcd(a, b)不能整除n，则方程无解；反之，通过将方程两边除以gcd(a, b)并应用扩展欧几里德算法，我们可以找到所有整数解。在提供的代码中，`extend_Euclid`函数实现了这个过程，返回了最大公约数以及一组特定的解。 中国同余定理（Chinese Remainder Theorem，CRT）是数论中的一个重要工具，它解决了模线性同余方程组的问题。例如，在Poj2891这样的编程竞赛题目中，可能需要应用中国同余定理来求解一系列模同余关系。在给出的代码中，`GCD`和`extend_Euclid`函数为实现CRT提供了基础，但没有展示完整的CRT应用。 原根（Primitive Root）是模p下的一个数，其幂次能覆盖所有非零模p剩余类。寻找原根在加密算法和数论问题中具有重要应用，但这个主题在摘要中未详细展开。 积性函数（Multiplicative Function）是一类特殊的数论函数，其值依赖于因数的性质，如欧拉函数phi(n)就是积性函数，它表示小于等于n且与n互质的正整数的数量。欧拉函数在数论中有着广泛应用，例如在计算群的阶或确定素数分布等方面。 欧拉函数的性质包括：对于素数p，phi(p) = p - 1；对于合数n，如果其因子分解为n = p1^k1 * p2^k2 * ... * pr^kr，那么phi(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pr)。线性求1-max的欧拉函数值通常涉及找到满足phi(n) % x == 0的最小正整数x，其中2^x ≡ 1 (mod n)。 这部分内容虽然简略，但展示了数论在算法和编程中的实际应用。通过深入学习这些概念，不仅可以理解基本的数论原理，还能提高解决相关算法问题的能力。在实际编程挑战中，如ACM/ICPC或OI比赛，掌握这些模板和方法对解决问题至关重要。