二次剩余即对常数 \(n\) 解这样的方程：\(x^2 \equiv n \pmod p\)。这里只讨论 \(p\) 为奇质数的情况。
二次剩余的数量
设方程 \(x^2 \equiv n \pmod p\) 存在多个解，那么显然任意两个模意义下的不同解 \(x_0, x_1\) 满足 \(x_0^2 \equiv x_1^2\)，得到 \(x_0 - x_1 \equiv 0\) 或 \(x_0 + x_1 \equiv 0\)。
对于前者，如果成立，则 \(x_0 = x_1 + kp\)，由于在模意义下，\(k\) 只能取 \(0\)，与 \(x_0 \not = x_1\) 矛盾。
于是任意两个解都互为相反数，这同样说明方程在 \([0, p - 1]\) 范围内只有 \(0\) 或 \(2\) 个解。
于是任意一对相反数都对应一个不同的二次剩余，也就是说 \(n \in [0, p - 1]\) 中二次剩余的数量为 \(\frac{p - 1}{2}\)。
欧拉准则
欧拉准则告诉我们：假定 \(n \not \equiv 0\)，若 \(n^{\frac{p - 1}{2}} \equiv 1\) 则 \(n\) 是二次剩余；若 \(n^{\frac{p - 1}{2}} \equiv -1\) 则 \(n\) 不是二次剩余。证明如下。
由欧拉定理， \(n^{p - 1} \equiv 1\)，则 \(n^{\frac{p - 1}{2}} \equiv \pm 1\)。设 \(n \equiv g^k\)，其中 \(g\) 是模 \(p\) 意义下的原根（此时 \(g^0 \sim g^{p - 1}\) 显然取遍 \(0 \sim p - 1\)）。
那么 \(n^{\frac{p - 1}{2}} \equiv g^{\frac{p - 1}{2} \times k} \equiv (-1)^k\)。当 \(k\) 为偶数时 \(n^{\frac{p - 1}{2}} \equiv 1\)，反之 \(n^{\frac{p - 1}{2}} \equiv -1\)。
若 \(n\) 为二次剩余，则 \(n \equiv g^k \equiv x^2\)，要求 \(k\) 为偶数。因此当 \(k\) 为偶数也就是 \(n^{\frac{p - 1}{2}} \equiv 1\) 时 \(n\) 是二次剩余，反之亦然。
于是我们证明了欧拉准则。
Cipolla
以上前置都是为解方程 \(x^2 \equiv n \pmod p\) 做准备。首先直接枚举解是不可能的，于是考虑找一个不是二次剩余的数。
先随机出一个 \(a\) 满足 \(a^2 - n\) 不是二次剩余，由于非二次剩余的数量为 \(\frac{p + 1}{2}\)，期望只需要两次就可以找到。
令 \(i^2 = a^2 - n\)（其实我不是很明白这么做的动机是什么），我们用类似复平面的定义，将所有数表示为 \(A + Bi\)，也就是扩域。其中 \(A\) 与 \(B\) 都是模意义下的数。
引理 \(1\)：\(i^p \equiv -i\)
证明：\(i^p \equiv i(i^2)^{\frac{p - 1}{2}} \equiv -i\)，这里运用到了欧拉准则。
引理 \(2\)：\((A + B)^p \equiv A^p + B^p\)
证明：二项式定理展开后除了 \(\binom{p}{0}\) 和 \(\binom{p}{p}\) 所对项外，一定包含因子 \(p\)，在模意义下为 \(0\)。
根据上述引理，我们可以说明 \((a + i)^{p + 1} \equiv (a+i)^p(a + i) \equiv (a - i)(a + i) \equiv a^2 - i^2 \equiv n\)。这里由于 \(a^{p - 1} \equiv 1\)，因此 \(a^p \equiv a\)。
那么 \((a + i)^\frac{p + 1}{2}\) 就是一个解，这里还要说明 \((a + i)^{\frac{p + 1}{2}}\) 的虚部为 \(0\)。
设 \((a + i)^{\frac{p + 1}{2}} = A + Bi\)，那么 \((A + Bi)^2 \equiv n\)，得到 \(A^2 + B^2(a^2 - n) - n \equiv 2ABi\)。
这里由于左边虚部为 \(0\)，那么右边虚部 \(2AB \equiv 0\)。又由于 \(\gcd(2, p) = 1\)，因此 \(AB \equiv 0\)。若 \(B \not = 0\)，则 \(A \equiv 0\)，于是 \(B^2i^2 \equiv n\)。
此时 \(i^2 \equiv nB^{-2}\)，显然右边两项都为二次剩余，于是左边也是二次剩余，这与 \(i^2\) 非二次剩余矛盾，因此 \(B = 0\)。
最终，我们酣畅淋漓地得到了方程的解 \((a + i)^{\frac{p + 1}{2}}\) 与它的相反数。
模板
mt19937_64 sj(chrono::steady_clock::now().time_since_epoch().count());int sqI, n, p;
struct Complex {int A, B;Complex(int _A = 0, int _B = 0): A(_A), B(_B) {}
};
bool operator == (Complex X, Complex Y) { return X.A == Y.A && X.B == Y.B; }
Complex operator * (Complex X, Complex Y) { return Complex((X.A * Y.A + X.B * Y.B % p * sqI) % p, (X.A * Y.B + X.B * Y.A) % p);
}Complex qmi(Complex a, int b) {Complex res = 1;for (; b; b >>= 1, a = a * a) if (b & 1) res = res * a;return res;
};bool check(int x) { return qmi(x, p - 1 >> 1) == 1; }void solve() {cin >> n >> p;if (!n) return cout << 0 << endl, void();if (!check(n)) return cout << "Hola!" << endl, void();uniform_int_distribution<LL> u0(0, p - 1);int a = u0(sj); while (!a || check((a * a - n + p) % p)) a = u0(sj);sqI = (a * a - n + p) % p; int x0 = qmi(Complex(a, 1), p + 1 >> 1).A, x1 = p - x0;if (x0 == x1) cout << x0 << endl;else cout << min(x0, x1) << ' ' << max(x0, x1) << endl;
}