转载注明来源：https://www.cnblogs.com/syc233/p/13741831.html
二次剩余，之前从数竞同学那听到过这个东西，觉得在OI中没啥用。直到今天T1考了二次剩余，我才流下了没有数理基础的眼泪。
二次剩余，其实就是模意义下开根。
给定常数 (n) ，解同余方程：
当存在 (x) 满足上式时，则 (n) 是模 (p) 的二次剩余。
否则 (n) 是模 (p) 的二次非剩余。
为了方便，下面的同余式均省略 (({ m{mod}} p)) 。
基本结论
这里只讨论 (p) 为奇素数的情况。
两个二次剩余的乘积必然还是二次剩余
证明略。
二次剩余的逆元还是二次剩余
证明略。
满足 “ (n) 是模 (p) 的二次剩余“ 的 (n) 有 (frac{p+1}{2}) 个
对于同余方程 (x^2equiv n) ，假设有两个解 (x_1,x_2) ，则易证 (x_1+x_2equiv 0) ，即 (x_1) 和 (x_2) 互为相反数。
那么这样的解的对数有 (p+1) 对，每一个 (n) 对应了两个解，那么 (n) 有 (frac{p+1}{2}) 个。
欧拉准则
勒让德符号 ({displaystyle ({frac {a}{p}})}) 定义：
欧拉准则：
那么若 (n) 是二次剩余，则 (n^{frac{p-1}{2}}=1) 。
证明：
由费马小定理 (n^{p-1}equiv 1) ，则 ((n^{frac{p-1}{2}})^2 equiv 1) 。那么 (n^{frac{p-1}{2}}) 是 (1) 模 (p) 意义下开根的结果，则 (n^{frac{p-1}{2}}=pm 1) 。
若 (n^{frac{p-1}{2}}=1) ，则令 (n=g^k) ，其中 (g) 为 (p) 的原根。
则有 ((g^k)^{frac{p-1}{2}}equiv 1) ，因为 (g^{p-1}equiv 1) 且 (g) 是原根，那么有 (p-1|k imesfrac{p-1}{2}) ，则 (k) 是偶数， (n) 开根的结果是 (g^{frac{k}{2}}) 。
所以 (n^{frac{p-1}{2}}=1) 时，(n) 是二次剩余，否则 (n) 是二次非剩余。
证毕。
求解 (x^2 equiv n ({ m{mod}} p))
先找出一个数 (a) ，满足 (a^2-n) 为二次非剩余，随机出一个数再判断即可。
令 (i^2equiv a^2-n) ，类比复数的定义，将所有数定义成 (A+Bi) 的形式。
那么 ((a+i)^{frac{p+1}{2}}) 是原方程的一个解。
证明：
相当于证明 ((a+i)^{p+1} equiv n) 。
则有：
由卢卡斯定理可得：
由费马小定理有 (a^p equiv a) 。则：
得证 ((a+i)^{p+1} equiv n) 。
证毕。
((a+i)^{frac{p+1}{2}}) 中虚部一定为 (0) 。
证明：
假设存在 ((A+Bi)^2equiv n,B ot =0) ，那么：
因为式子左边虚部为 (0) ，所以式子右边虚部也应该为 (0) ，则 (A=0) 。
得到 (i^2equiv n imes B^{-2}) ，因为右边是两个二次剩余，所以 (i^2) 也是二次剩余，与 (i) 的定义矛盾，所以 (B=0) 。
证毕。
( ext{Code}:)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define Rint register int
#define INF 0x3f3f3f3f
using namespace std;
typedef long long lxl;
template <typename T>
inline void read(T &x)
{
x=0;T f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
x*=f;
}
lxl n,p,w;
struct Complex
{
lxl x,y;
Complex(lxl x,lxl y):x(x),y(y){}
Complex(){}
inline Complex operator * (const Complex &T)const
{
return Complex((x*T.x%p+y*T.y%p*w%p)%p,(x*T.y%p+y*T.x%p)%p);
}
};
inline lxl fmi(lxl a,lxl b)
{
lxl res(1);
a%=p;
while(b>0)
{
if(b&1) (res*=a)%=p;
(a*=a)%=p;
b>>=1;
}
return res;
}
inline Complex cfmi(Complex a,lxl b)
{
Complex res(1,0);
while(b>0)
{
if(b&1) res=res*a;
a=a*a;
b>>=1;
}
return res;
}
inline lxl Sqrt(lxl n,lxl p) // 在模 p 意义下开根
{
n=(n%p+p)%p;
if(!n) return 0;
if(fmi(n,(p-1)>>1)!=1) return -1;
lxl a;
while(1)
{
a=rand()%p;
w=(a*a%p-n+p)%p;
if(fmi(w,(p-1)>>1)!=1) break;
}
return cfmi(Complex(a,1),(p+1)>>1).x;
}
int main()
{
// freopen("P5491.in","r",stdin);
int T;read(T);
while(T--)
{
read(n),read(p);
lxl x1=Sqrt(n,p),x2=(p-x1)%p;
if(!~x1) puts("Hola!");
else if(x1==x2) printf("%lld
",x1);
else printf("%lld %lld
",min(x1,x2),max(x1,x2));
}
return 0;
}