题目链接
https://cn.vjudge.net/problem/URAL-1132
题意
求解方程 $x^2\equiv t\pmod{p}$
题解
欧拉准则：
令勒让德符号 $\left(\frac{t}{p} \right)=t^{\frac{p-1}{2}}\bmod p$
当 $\left(\frac{t}{p}\right)=0$ 时， $p|t$
当 $\left(\frac{t}{p}\right)=1$ 时， $t$ 为二次剩余
当 $\left(\frac{t}{p}\right)=-1$ 时， $t$ 为非二次剩余
证明：
$t$ 与 $p$ 不互质显然$\left(\frac{t}{p}\right)=0$
当 $t$ 与 $p$ 互质
所以
必要性：
当 $t$ 为二次剩余，那么存在 $x$ ，满足
充分性：
令 $g$ 为 $p$ 的一个原根，且 $t=g^k$ ，那么
由于 $g$ 的指标是 $p-1$ ，所以 $\frac{k(p-1)}{2}|(p-1)$ ，即 $\frac{k}{2}|1$
所以 $k|2$ ，$t$ 为一个二次剩余
那么 $-1$ 的情况也一起证明了
有这个结论就可以用于构造了，任取一个数 $a$ ，满足 $w=a^2-t$ 为一个非二次剩余，那么 $x=(a+\sqrt w)^{\frac{p+1}{2}}$ 为一个二次剩余方程的解
证明：
首先证明 $(a+b)^p\equiv a^p+b^p\pmod p$
这个其实模方程的一个结论，因为展开之后会有二项式系数 $\binom{p}{i}$ ，由于 $p$ 为素数，所以只有第一项和最后一项不会被 $p$ 整除
然后有
可是既然 $w$ 是非二次剩余，那又如何用 $\sqrt w$ 计算呢？把他们都看成 $x+y\sqrt w$ 的形式，不管这个数做何种运算，都会像复数一样最终化成 $x+y\sqrt w$ 的形式，因此只要算系数 $x$ 和 $y$ 就可以了，然后直接做快速幂即可。。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<set>
#include<bitset>
#include<complex>
#include<cstdlib>
#include<assert.h>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-8
#define succ(x) (1<<x)
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define NM 5005
#define nm 4005
using namespace std;
const double pi=acos(-1);
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
ll _t,inf;
ll qpow(ll x,ll t){return t?qpow(sqr(x)%inf,t>>1)*(t&1?x:1ll)%inf:1ll;}
ll Sqrt(ll t,ll inf){
ll a=0,w;
if(qpow(t,inf-1>>1)+1==inf)return -1;
do{
a=rand()%inf;
w=(sqr(a)-t+inf)%inf;
}while(qpow(w,inf-1>>1)+1!=inf);
ll ans=1,_ans=0,_x,_y;
for(ll n=inf+1>>1,x=a,y=1;n;n>>=1){
if(n&1){
_x=ans*x%inf+_ans*y%inf*w%inf;
_y=ans*y%inf+_ans*x%inf;
ans=_x%inf;_ans=_y%inf;
}
_x=x*x%inf+y*y%inf*w%inf;
_y=2*x*y%inf;
x=_x%inf;y=_y%inf;
}
return ans;
}
int main(){
int _=read();while(_--){
_t=read();inf=read();_t%=inf;
if(inf==2){printf("1\n");continue;}
ll ans=Sqrt(_t,inf);
if(ans==-1)puts("No root");else{
_t=inf-ans;
if(ans>_t)swap(_t,ans);
if(ans==_t)printf("%lld\n",ans);
else printf("%lld %lld\n",ans,_t);
}
}
return 0;
}
|
