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
| typedef long long ll;
struct cp{
static ll p,w;
ll x,y;
cp(ll x,ll y):x(x),y(y){}
cp operator*(cp rhs){
return cp((x*rhs.x+y*rhs.y%p*w)%p,(x*rhs.y+y*rhs.x)%p);
}
};
ll cp::p,cp::w;
cp qpow(cp a,ll b){
cp res(1,0);
for(;b;b>>=1,a=a*a) if(b&1)res=res*a;
return res;
}
ll qpow(ll a,ll b,ll p){
ll res=1;
for(;b;b>>=1,a=a*a%p) if(b&1)res=res*a%p;
return res;
}
ll sqrt(ll x,ll p){
if(x==0) return 0;
if(qpow(x,(p-1)/2,p)==p-1)return -1;
ll a=1,w=(1-x+p)%p;
while(qpow(w,(p-1)/2,p)!=p-1) ++a,w=(a*a-x+p)%p;
cp::w=w,cp::p=p;
return qpow(cp(a,1),(p+1)/2).x;
}
|