二次剩余 学习笔记
退役前挣扎一下 说起来高一寒假就学过一次这玩意,学一次忘一次 其实就是求$x^2 \equiv a \pmod p$。 有不少算法的样子,比较常用的应该是Cipolla算法,可以求解模奇素数的二次剩余。 首先冷静一下:考虑原根,那么就是要求$2x’ \equiv a’ \pmod \varphi$。因为$\varphi$是偶数,所以一半的$a$有解,且有两组解。 欧拉判别准则: 考虑$a^{\frac{p-1}{2}}$,如果等于$1$,说明$a$存在二次剩余,否则不存在。 证明:用$x^2$替换$a$带入,发现等于$-1$的时候$x$不存在 于是可以得到这样的算法: 求解$x^2 \equiv n \pmod p$ 找到一个数$a$,使得$a^2 - n$非二次剩余,定义$i^2 \equiv a^2 - n$(类似虚数)。 那么有$(a+i)^{\frac{p+1}{2}}$及其相反数是$n$的二次剩余。 证明: 考虑使用二项式定理展开。由Lucas定理,可以发现大部分项的组合数都是$0$。化简得: $$\binom10 \binom10 \sqrt{a^2 - n}^{p+1} + \binom10 \binom11 a \sqrt{a^2 - n}^p + \binom11 \binom10 a^p \sqrt{a^2-n} + \binom11 \binom11 a^{p+1}$$ 大力化简一下,得到这个式子就是$n$。 于是直接模拟以上算法即可。复杂度期望$O(logn)$。 例题:SCOI2018 Numazu 的蜜柑 好像没啥好写的啊。。推推式子,发现可以在祖先处解一个方程,并查询子树里有多少符合条件的。启发式合并即可。 这个代码是板子
1 |
|