二次剩余算法
解决的问题:
形如:求是否存在x满足 : x^2 = n (mod p)
https://www.luogu.com.cn/problem/P5491
模板:
ll n,p;
ll w;
struct num{ //负数
ll x,y;
};
num mul(num a,num b,ll p){
num ans = {0,0};
ans.x = ((a.x*b.x%p+a.y*b.y%p*w%p)%p+p)%p;
ans.y = ((a.x*b.y%p+a.y*b.x%p)%p+p)%p;
return ans;
}
ll qpw(ll a,ll b,ll p){
ll ans=1;
while(b){
if(b&1)ans=ans%p*a%p;
a=a%p*a%p;
b>>=1;
}
return ans%p;
}
ll qpwii(num a,ll b,ll p){ //复数的快速幂
num ans={1,0};
while(b){
if(b&1)ans=mul(ans,a,p);
a=mul(a,a,p);
b>>=1;
}
return ans.x%p;
}
ll solve(ll n,ll p){ //x^2 = n (mod p)
n %= p;
if(p == 2)return n;
if(qpw(n,(p-1)/2,p) == p-1)return -1;
ll a;
while(1){
a = rand()%p;
w=((a*a%p-n)%p+p)%p;
if(qpw(w,(p-1)/2,p) == p-1)break;
}
num x = {a,1};
return qpwii(x,(p+1)/2,p);
}
void work() {
scanf("%lld%lld",&n,&p);
if(!n) {
printf("0\n");
return ;
}
ll ans1 = solve(n,p),ans2;
if(ans1 == -1)printf("Hola!\n");
else{
ans2 = p - ans1;
if(ans1 > ans2)swap(ans1,ans2);
if(ans1 == ans2)printf("%lld\n",ans1);
else printf("%lld %lld\n",ans1,ans2);
}
}