《算法竞赛中的初等数论》（七）剩余章节（0x70 - 0xA0）1
需积分: 0 16 浏览量
2022-08-03
22:12:52
上传
评论
收藏 1.92MB PDF 举报
0x70 二次剩余
0x71 二次剩余与二次非剩余
定义
对于二次同余方程 有解，则称 为 的二次剩余， 为该二次同余方程的解。
二次剩余 ，就是一个二次项 后的剩余。
当对任意 ， 不成立时，称 是模 的二次非剩余。
应用
求 ，若 为 的二次剩余，则 。
即：若该二次同余方程有解，则 可以在模 的意义下开根。
0x72 Cipolla 算法解算法二次同余方程
需要保证模 是奇素数。
引入勒让德符号：
表示 是否为 的二次剩余， 和 表示是与否， 表示 的情况。
定理
定理72.1：
定理72.2： 若找到一个 使得 , 且 则 为
的解
定理72.3： 对于二次同余方程 有 个 使此方程有解
实现
求解方程 。保证 是奇素数。 输入一个 代表数据组数，接下来 行，每
行一个 和一个 。 对于每一行输出：若有解，则按 后递增的顺序输出在
意义下的全部解. 若两解相同，只输出其中一个 若无解，则输出
N
o
S
olution
有了上面的三个定理，现在我们的唯一问题就是如何找到合适的 使得 满足条件，我们考虑随机，
由定理72.3可知， 在模p意义下为非二次剩余的概率为 ，那么这样随机的期望次数就接
近于 ，可以看做是 求。因为在整个过程中使用过快速幂，所以时间复杂度为 。
int
mod
;
ll
I
_
mul
_
I
;
虚数单位的平方
stru
c
t
C
omplex
{
建议自己实现复数
ll
re
a
l
,
im
a
g
;
C
omplex
(
ll
re
a
l
=
0
,
ll
im
a
g
=
0
):
re
a
l
(
re
a
l
),
im
a
g
(
im
a
g
) { }
1
2
3
4
5
剩余21页未读，继续阅读
评论0