《算法竞赛中的初等数论》（七）剩余章节（0x70 - 0xA0）1

《算法竞赛中的初等数论》（七）剩余章节（0x70 - 0xA0）1 本文主要探讨了算法竞赛中涉及到的初等数论知识，特别是关于二次剩余的问题及其解决方法。二次剩余是数论中的一个重要概念，它涉及到模运算和二次同余方程。 0x70 二次剩余：在数论中，如果存在整数 \( x \)，使得 \( x^2 \equiv a \mod p \) 成立，其中 \( p \) 是一个质数，那么 \( a \) 就是模 \( p \) 的二次剩余。相反，如果不存在这样的 \( x \)，则 \( a \) 是模 \( p \) 的二次非剩余。 0x71 二次剩余与二次非剩余的性质：如果 \( a \) 是 \( p \) 的二次剩余，那么 \( p \) 可以在模 \( p \) 的意义下开平方根，即存在整数 \( x \)，满足 \( x^2 \equiv a \mod p \)。而当 \( a \) 对任意 \( x \) 都不满足 \( x^2 \equiv a \mod p \) 时，\( a \) 为二次非剩余。 0x72 Cipolla 算法：Cipolla 算法用于求解二次同余方程 \( ax^2 \equiv b \mod p \)，其中 \( p \) 是奇素数。算法的核心是勒让德符号，它表示一个数是否为模 \( p \) 的二次剩余。勒让德符号 \( \left(\frac{a}{p}\right) \) 的值可以是 1（表示 \( a \) 是二次剩余），-1（表示 \( a \) 是二次非剩余），或者 0（表示 \( a \) 与 \( p \) 有公因数）。根据定理72.1和72.2，我们可以找到满足特定条件的 \( a' \)，从而解出 \( x \)。 定理72.1：勒让德符号的乘法规则。 定理72.2：如果 \( \left(\frac{a}{p}\right) = 1 \) 并且存在 \( x \) 使得 \( a \equiv x^2 \mod p \)，那么 \( a \) 是 \( p \) 的二次剩余。 定理72.3：对于二次同余方程 \( ax^2 \equiv b \mod p \)，存在 \( \sqrt{a} \) 个解，这些解可以通过特定方式构造出来。 在实现过程中，我们通常会使用快速幂算法来高效地计算 \( x^k \mod p \)。Cipolla 算法的时间复杂度约为 \( O(\log p) \)，因为主要依赖于快速幂运算。 0x80 某些非线性丢番图方程和0x81 毕达哥斯拉三元组（勾股数）虽然没有详细展开，但它们也是数论中的经典问题，涉及寻找满足特定条件的整数解。毕达哥斯拉三元组是指满足 \( a^2 + b^2 = c^2 \) 的整数 \( (a, b, c) \)。 这部分内容介绍了算法竞赛中初等数论的应用，尤其是如何利用数论知识解决实际问题，如求解二次同余方程。掌握这些概念和方法对于参加算法竞赛或解决相关问题具有重要意义。