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

"ACM数论模板" 在ACM竞赛或算法设计中，数论是不可或缺的一部分，本资源提供了几个关键的数论概念和算法模板，包括扩展的欧几里德算法、中国同余定理、原根、积性函数、欧拉函数及其性质、线性求欧拉函数值以及求解特定形式的不定方程。这些知识点在解决数论问题时非常有用。 1. **扩展的欧几里德和不定方程的解** 扩展的欧几里德算法是用来求解最大公约数(Greatest Common Divisor, GCD)的同时，找到贝祖等式(ax + by = gcd(a, b))的一组解。这里的代码实现了一个递归版本的扩展欧几里德算法，用于求解x和y。通过这个算法，可以解决不定方程ax + by = n的问题，当gcd(a, b)能整除n时，存在整数解，并可通过公式推导出所有解。 2. **中国同余定理** 中国同余定理（Chinese Remainder Theorem, CRT）是数论中的一个重要定理，它允许我们将多个同余方程组的问题转化为单一的同余方程。在给出的代码中，展示了如何应用扩展欧几里德算法来求解基于CRT的问题。在Poj2891这个题目中，可能需要处理多个模意义下的同余关系，中国同余定理提供了有效的解决方案。 3. **原根** 原根（Primitive Root）是指在一个模p的剩余类环中，能够生成所有非零元素的乘法群的一个元素。原根在密码学和编码理论中有重要应用。虽然这里没有详细讨论原根的计算方法，但它是数论模板中不可或缺的概念。 4. **积性函数** 积性函数是一种只依赖于其参数的素因数分解的函数，例如欧拉函数φ(n)就是一个典型的积性函数。积性函数的性质对于理解和计算与数的因子有关的问题非常有帮助。 5. **欧拉函数性质** 欧拉函数φ(n)表示小于等于n且与n互质的正整数的数量。它在数论中有着丰富的性质，如φ(p^n) = p^n - p^(n-1)（其中p是素数），以及欧拉定理：如果a和n互质，则a^φ(n) ≡ 1 (mod n)。求解φ(n)的线性形式以及找到满足2^x = 1 (mod n)的最小x，都是数论问题中常见的任务。 6. **线性求1-max的欧拉函数值** 这部分可能涉及到求解欧拉函数在一定范围内的最大值或者与某个特定值的相对关系，比如找出使得2^x对n取模等于1的最小正整数x。 7. **求单个欧拉函数** 求解欧拉函数φ(n)通常需要考虑n的素因子分解，一旦知道n的质因数分解，就可以方便地计算出φ(n)的值。 以上知识点是ACM竞赛中数论部分的基础，掌握它们有助于解决涉及数论的复杂算法问题。在实际编程中，理解并熟练运用这些模板可以提高解决问题的效率。