ffffyc 的基地

ffffyc 的基地

JRKSJ 出题组最弱的出题人

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

posted on 2021-03-04 18:41:28 | under 题解 |

传送门

板子题。

题意

给出 $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$

$(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<-

代码不放,想要看可以去上面链接中的文章最下方的链接里看,稍作修改即可。

若我有表述不清,可以去上面链接中的文章中看。

再见qwq~