传送门
板子题。
题意
给出 a,p，求满足 x^2\equiv a(\bmod p) 的所有 x。
模奇素数的二次剩余大家都讲过了，这里不再多说。
我们来看任意模数二次剩余。
思路
我们将上面的问题拆分为四部分：
1.p 为奇素数
不讲，见其他题解。
2.p=p_0^k，其中 p_0 为奇素数
设 a=p_0^i\times m,p_0\nmid m。
当 i\ne0 时：
设 x=p_0^j\times n,p_0\nmid n,即 x^2=p_0^{2j}n^2
于是有当 $x_0^2\equiv \dfrac{a}{p^i}(\bmod p_0^{k-i})$ 有解时原方程有解 $x=x_0p^{\frac i 2}$，注意 $2\mid i$ 时才有解。
注意欧拉定则的 $p-1$ 需要换成 $\phi(p_0^{k-i})$。
当 $i=0$ 时：
先解二次剩余
$$q^2\equiv a(\bmod p_0)$$
有：
$$(q^2-a)^k\equiv0(\bmod p)$$
设
$$(q^2-a)^k\equiv s^2-t^2a(\bmod p)$$
有
$$(q-\sqrt a)^k=s-t\sqrt a$$
$$(q+\sqrt a)^k=s+t\sqrt a$$
所以有
$$s^2\equiv t^2a(\bmod p)$$
$$s^2t^{-2}\equiv a(\bmod p)$$
显然逆元有解。
时间复杂度 $O(\log p)
3.p=2^k
先将 a 中 2 的因数除掉，然后可以发现 a\equiv 1(\bmod 8) 才有解。
证明：
因为 x_0^2\equiv a(\bmod p),2\nmid a，所以 2\nmid x_0
，设 x_0=2q+1。
求解：
对 $k$ 分类讨论，
当 $k\le 3$ 时，特判即可。
当 $k>3$ 时，
设解可以表示为 $x_0=±(x_{q-1}+t_{q-1}\times 2^{q-2})
对于 x^2\equiv a(\bmod 2^{q-1}) 的解 x_{q-1}，有：
x_{q-1}^2\equiv a\bmod 2^{q-1}(\bmod 2^q)
或
x_{q-1}^2\equiv a\bmod 2^{q-1}+2^{q-1}(\bmod 2^q)
我们要求出 t_{q-1}，带入方程 x^2\equiv a(\bmod 2^{q}) 有
t_{q-1}\equiv \dfrac{a\bmod 2^q-x_{q-1}^2}{2^{q-1}}(\bmod 2)
所以满足要求的 t_{q-1}=\dfrac{a\bmod 2^q-x_{q-1}^2}{2^{q-1}}+2\times t_q.
带回方程 x^2\equiv a(\bmod 2^{q}) 得到解为：
x=±(x_{q-1}+\dfrac{a\bmod 2^q-x_{q-1}^2}{2}+2^{k-1}\times t_k)
从 q=3 开始递推就行了。
时间复杂度 O(\log p)，也就是 O(k)。
4.p 无要求
分解 p 得到 t 个二次剩余方程
\begin{cases}x_1^2\equiv a(\bmod p_1^{k_1})\\x_2^2\equiv a(\bmod p_2^{k_2})\\x_3^2\equiv a(\bmod p_3^{k_3})\\...\\x_t^2\equiv a(\bmod p_t^{k_t})\end{cases}
最后用 CRT 合并：
\begin{cases}x\equiv x_1(\bmod p_1^{k_1})\\x\equiv x_2(\bmod p_2^{k_2})\\x\equiv x_3(\bmod p_3^{k_3})\\...\\x\equiv x_t(\bmod p_t^{k_t})\end{cases}
本文参考：->Click Here<-
代码不放，想要看可以去上面链接中的文章最下方的链接里看，稍作修改即可。
若我有表述不清，可以去上面链接中的文章中看。
再见qwq~