二次剩余(懒人模板总结)

只考虑奇质数的情况

设求a(modP)

Part1 判断

存在二次剩余即a(P1)2=1(modP)


(对于所有a=0,1的情况需要特判)

Part2 原根法求二次剩余

先求出P的一个原根g

那么可以用gk表示出[1,P1]的所有数

BSGS可以在O(nlogn)的时间内求出a=gk

如果存在原根,那么kmod2=0

答案就是gk2modP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Quad(int a,int k=0) {
if(a<=1) return a;
int g=Getg(P);
static map <int,int> M;
int S=sqrt(P-1);
for(int i=0,t=1;i<S;++i,t=1ll*t*g%P) M[t]=i;
int res=0;
int w=qpow(g,S);
for(int i=0,t=1;i<P-1;i+=S,t=1ll*t*w%P) {
ll x=1ll*a*qpow(t,P-2)%P;
if(M.count(x)) {
res=M[x]+i;
break;
}
}
res=qpow(g,res/2);
if(k) res=min(res,(P-res)%P);
return res;
}

Part3 更快的方法

要先找到一个数x,满足不存在x2a(modP)

可以随机x,期望可以在O(1)时间内找到这样的x

然后构造复数(α,β)=α+x2aβ

求出(x,1)(P+1)2,模拟复数乘法即可

可以证明结果没有虚部,就是答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int Quad(int a,int k=0) {
if(a<=1) return a;
ll x;
while(1) {
x=1ll*rand()*rand()%P;
if(qpow((x*x-a+P)%P,(P-1)/2)!=1) break;
}
ll w=(x*x-a+P)%P;
Pii res=mp(1,0),t=mp(x,1);
auto Mul=[&](Pii a,Pii b){ // 复数乘法
int x=(1ll*a.first*b.first+1ll*a.second*b.second%P*w)%P;
int y=(1ll*a.first*b.second+1ll*a.second*b.first)%P;
return mp(x,y);
};
int d=(P+1)/2;
while(d) {
if(d&1) res=Mul(res,t);
t=Mul(t,t);
d>>=1;
}
ll r=(res.first%P+P)%P;
if(k) r=min(r,(P-r)%P);
return r;
}