在CSP - J备考的强化阶段（第3 - 4个月），数学部分的二次剩余是一个重要的知识点。
一、二次剩余的定义
二次剩余的概念是如果同余方程(x^{2}\equiv n\ mod\ p)有解，那么(n)就被称为模(p)的二次剩余。这里的(p)是一个质数。例如，当(p = 5)时，(n = 4)就是模(5)的二次剩余，因为(x = 2)或者(x = 3)时，(2^{2}=4\equiv4\ mod\ 5)，(3^{2}=9\equiv4\ mod\ 5)。这个概念的理解关键在于从方程的解的角度出发，去判断一个数在模某个质数的情况下是否为二次剩余。
二、欧拉判别法
1. 知识点内容
- 欧拉判别法指出对于同余方程(x^{2}\equiv n\ mod\ p)（(p)为质数），(n)是模(p)的二次剩余当且仅当(n^{((p - 1)/2)}\equiv1\ mod\ p)。
- 例如，当(p = 7)，(n = 2)时，计算(2^{((7 - 1)/2)}=2^{3}=8\equiv1\ mod\ 7)，所以(2)是模(7)的二次剩余。
2. 学习方法
- 要深入理解这个判别法的原理，需要先掌握指数运算在模运算下的性质。可以通过多做一些简单的例子，从较小的质数开始计算，观察结果，从而加深对判别法的理解。
- 记忆这个判别法的公式时，可以结合具体的计算过程，而不是单纯死记硬背公式。
三、Tonelli - Shanks算法
1. 知识点内容
- 当确定(n)是模(p)的二次剩余后，Tonelli - Shanks算法可以用来求解同余方程(x^{2}\equiv n\ mod\ p)的解。这个算法相对复杂一些，它的基本步骤包括将(p - 1)分解成(2^{s}\times q)的形式（其中(q)是奇数），然后通过一系列的计算找到原根等相关操作来求解(x)。
2. 学习方法
- 对于这个算法的学习，首先要对数论中的一些基础概念如原根有清晰的认识。可以通过查阅相关的数学教材或者网上的优质教程，仔细研读算法的每一个步骤。
- 自己动手编写代码实现这个算法也是很好的学习方法，在编写过程中能够更深入地理解算法的逻辑。同时，做一些针对性的练习题，用Tonelli - Shanks算法去求解给定的二次剩余方程，提高解题能力。
二次剩余作为数论中的扩展知识，在CSP - J的备考中是需要我们掌握的基本概念。通过深入理解定义、熟练运用欧拉判别法以及掌握Tonelli - Shanks算法，能够在遇到相关的数学问题时更加从容地应对，提高我们在信息学奥赛中的竞争力。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
