题解 P5491【【模板】二次剩余】

[_传送门_](https://www.luogu.com.cn/problem/P5491) 板子题。 ## 题意 给出 $a,p$，求满足 $x^2\equiv a(\bmod p)$ 的所有 $x$。 模奇素数的二次剩余大家都讲过了，这里不再多说。 我们来看[任意模数二次剩余](https://www.luogu.com.cn/problem/U152928)。 ## 思路 我们将上面的问题拆分为四部分： #### 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$ $(p_0^{2j}n^2)\bmod p=p^{2j}(n^2\bmod p_0^{k-2j})$，即 $p_0^{2t}\mid a$. 于是有当 $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$。 $a\equiv(2q+1)^2=4q(q+1)+1(\bmod p)$，我们有 $8\mid 4q(q+1)$，所以 $a\equiv 1(\bmod 8)$ 时原方程有解。 求解： 对 $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<-](https://blog.csdn.net/zxyoi_dreamer/article/details/85195819) 代码不放，想要看可以去上面链接中的文章最下方的链接里看，稍作修改即可。 若我有表述不清，可以去上面链接中的文章中看。 再见qwq~