学习博客：https://blog.csdn.net/stevensonson/article/details/85845334
之前就想学过，但是是在 (oiwiki) 上学的，那个其实写的有些错误，而且挺难懂的，所以还是推荐自己找博客学习。
什么是二次剩余？
如果存在一个整数 (x)，满足 (x^2equiv n \,(mod \,p)) ，那么称 (n) 是模 (p) 的二次剩余。
对于方程 (x^2equiv n \,(mod \,p)) ，有 (frac{p-1}{2}) 不同的 (n) ,使得方程有解
首先明确不考虑 (n==0) (二次剩余的定义)
因为对于一个(u)，如果大于 (p)，即(u=x*p+y) ，模 (p) 之后等价于 (y)，所以我们首先将 (u) 限制在 ([1,p-1]) 这个范围内。
首先证明有两个解：
(u^2equiv n \,mod \,p) ，那么一定存在 ((p-u)^2 equiv n \,mod\,p) 一定成立。
所以对于一个数 (n) ，如果存在解，那么至少存在两个。
再而证明最多两个解：
(x_1^2equiv n\,mod\,p) ，(x_2^2equiv n\,mod\,p)
那么 (x_2^2-x_1^2equiv 0\,mod\,p) ，所以 ((x_1+x_2)*(x_1-x_2)|p) ，因为 (0<x1,x2<p) ，所以 ((x_1+x_2)=p) ，这个解就是上式的 (u) 和 (p-u) ，所以最多只有两个解。
综上所述，所以有 $frac{p-1}{2} $二次剩余的解 (n) 在 ([1,p-1]) 中对应了两个数，所以一定存在 (frac{p-1}{2}) 个数没有在 ([1,p-1]) 中没对应数，那么这些数 (y) 永远不会对应任何 (x) 使得 (x^2equiv y \,mod\,p) ， 因为大于 (p-1) 的数都可转化到 ([0,p-1]) 中来。
判断一个数是否是模 (p) 的二次剩余，勒让德符号 (frac{n}{p})
如果 (n) 是模 (p) 的二次剩余，那么 (frac{n}{p}=1)
如果 (n) 不是模 (p) 的二次剩余，那么 (frac{n}{p}=-1)
如果 (p|n) ，那么 (frac{n}{p}=0)
结论：
如果p是一个奇质数，那么 (frac{n}{p}=n^{frac{p-1}{2}})
最后也是最重要的：求解二次剩余
在 ([0,p-1]) 随机挑一个数 (a) ，令 (w=a^2-n) ，如果 (w) 是模 (p) 的一个非二次剩余，那么 ((a+sqrt{w})^{frac{p+1}{2}}) 是一组二次剩余。
证明：
((a+sqrt{w})^p equiv a^p+(sqrt{w})^p\,mod\,p)
由费马小定理可得：(a^pequiv a\,mod\,p)
因为 (w) 是模 (p) 的一个非二次剩余，而 (p) 又是一个奇质数，所以 (w^{frac{p-1}{2}}=-1) 那么 (sqrt{w}^p=-sqrt{w})
所以 $(a+sqrt{w})^p equiv ap+(sqrt{w})p equiv (a-sqrt{w}),mod,p $
所以((a+sqrt{w})^{p+1} equiv (a-sqrt{w})*(a+sqrt{w}) equiv a^2-w equiv n \,mod\,p)
证毕！
struct num { //建立一个复数域
ll x, y;
};
ll w;
num mul(num a, num b, ll p) { //复数乘法
num ans = {0, 0};
ans.x = ((a.x * b.x % p + a.y * b.y % p * w % p) % p + p) % p;
ans.y = ((a.x * b.y % p + a.y * b.x % p) % p + p) % p;
return ans;
}
ll binpow_real(ll a, ll b, ll p) { //实部快速幂
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans % p;
}
ll binpow_imag(num a, ll b, ll p) { //虚部快速幂
num ans = {1, 0};
while (b) {
if (b & 1) ans = mul(ans, a, p);
a = mul(a, a, p);
b >>= 1;
}
return ans.x % p;
}
ll cipolla(ll n, ll p) {
n %= p;
if (p == 2) return n;
if (binpow_real(n, (p - 1) / 2, p) == p - 1) return -1;
ll a;
srand(time(NULL));
while (1) { //生成随机数再检验找到满足非二次剩余的a
a = rand() % p;
w = ((a * a % p - n) % p + p) % p;
if (binpow_real(w, (p - 1) / 2, p) == p - 1) break;
}
num x = {a, 1};
return binpow_imag(x, (p + 1) / 2, p);
}