正题
题目链接:https://www.luogu.com.cn/problem/P5491
题目大意
求解
x
2
=
N
(
m
o
d
P
)
x^2=N(mod\ \ P)
x2=N(mod P)
解题思路
若
a
a
a在模
p
p
p意义下可以开根那么
a
a
a就是
p
p
p的二次剩余，定义
(
a
p
)
=
{
1
(
a
是
p
的
二
次
剩
余
)
−
1
(
a
是
p
的
二
次
非
剩
余
)
0
(
p
∣
a
)
\binom{a}{p}=\left\{\begin{matrix}1(a是p的二次剩余)\\-1(a是p的二次非剩余)\\0(p|a)\end{matrix}\right.
(pa)=⎩⎨⎧1(a是p的二次剩余)−1(a是p的二次非剩余)0(p∣a)
那么如果
g
c
d
(
a
,
p
)
=
1
gcd(a,p)=1
gcd(a,p)=1就有
(
a
p
)
=
a
p
−
1
2
\binom{a}{p}=a^{\frac{p-1}2{}}
(pa)=a2p−1。
如果我们求
x
2
=
N
(
m
o
d
p
)
x^2=N(\mod p)
x2=N(modp)那么我们考虑先求一个
(
a
2
−
N
)
p
−
1
2
=
−
1
(a^2-N)^{\frac{p-1}{2}}=-1
(a2−N)2p−1=−1，然后定义
ω
=
a
2
−
N
\omega=\sqrt{a^2-N}
ω=a2−N
，那么就有定理
x
=
(
a
+
ω
)
p
+
1
2
x=(a+\omega)^{\frac{p+1}{2}}
x=(a+ω)2p+1，这里我们找
a
a
a的时候只要随机就好了，因为
p
p
p的二次有
p
+
1
2
\frac{p+1}{2}
2p+1个，期望很快就能找到一个合法的
a
a
a。
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std
;
ll T
,n
,p
,k
,w
;
struct complex
{
complex(ll xx
=0,ll yy
=0)
{x
=xx
;y
=yy
;}
ll x
,y
;
};
complex
operator+(complex
&a
,complex
&b
)
{return complex((a
.x
+b
.x
)%p
,(a
.y
+b
.y
)%p
);}
complex
operator-(complex
&a
,complex
&b
)
{return complex((a
.x
-b
.x
+p
)%p
,(a
.y
-b
.y
+p
)%p
);}
complex
operator*(complex
&a
,complex
&b
)
{return complex((a
.x
*b
.x
%p
+a
.y
*b
.y
%p
*w
%p
+p
)%p
,(a
.x
*b
.y
+a
.y
*b
.x
)%p
);}
complex
poweri(complex x
,ll b
){
complex ans
=complex(1,0);
while(b
){
if(b
&1)ans
=ans
*x
;
x
=x
*x
;b
>>=1;
}
return ans
;
}
ll
power(ll x
,ll b
){
ll ans
=1;
while(b
){
if(b
&1)ans
=ans
*x
%p
;
x
=x
*x
%p
;b
>>=1;
}
return ans
;
}
bool check(ll a
)
{return power(((a
*a
%p
-n
)%p
+p
)%p
,k
)==(p
-1);}
int main()
{
srand(31958);
scanf("%lld",&T
);
while(T
--){
scanf("%lld%lld",&n
,&p
);
if(!n
){printf("0\n");continue;}
if(p
==2){printf("%lld\n",n
);continue;}
k
=(p
-1)>>1;
if(power(n
,k
)==p
-1){printf("Hola!\n");continue;}
ll a
=rand()%p
;
while(!check(a
))a
=rand()%p
;w
=((a
*a
%p
-n
)%p
+p
)%p
;
ll x1
=poweri(complex(a
,1),(p
+1)/2).x
;
ll x2
=p
-x1
;if(x1
>x2
)swap(x1
,x2
);
if(x1
!=x2
)printf("%lld %lld\n",x1
,x2
);
else printf("%lld\n",x1
);
}
}
