二次剩余

整个算法可谓是神奇!!!!
算法流程:
1.判断当前是否是一个二次剩余用 n^(p-1)/2=p-1(mod p)来判如果等于那就不是直接返回无解
2.循环选取一个随机数并且计算它的w=a^2-n
3.判断w^(p-1)/2=p-1 (mod p)是否正确，如果对的话那么我们跳出
4.计算拓展数域上的 (a+w)^(p+1)/2 即可
拓展数域就是同余的拓展出来一个类似复数的数域，所以我们重载乘法 (a+iw) x (b+jw) = (ab+ijw^2)+(aj+bi)w
5.计算出来之后我们需要判断几个解如果p-拓展域实数位上的数=拓展域实数位上的数 也就是说ans.x=p-ans.x那么总共有一个解
6.否则那就两个解分别输出即可
证明看网上大佬吧…..

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,p,w,a;
struct node
{
	ll x,y;
};
node mul(node a,node b)
{
	return (node){(a.x*b.x%p+a.y*b.y%p*w%p)%p,(a.x*b.y%p+a.y*b.x%p)};
}
ll qpow(ll a,ll b)
{
	ll ans=1;
	ll base=a;
	while(b)
	{
		if(b&1)
		ans=ans%p*base%p,ans%=p;
		base=base%p*base%p,base%=p;
		b>>=1;
	}
	return ans%p;
}
node qmul(node a,int b)
{
	node ans={1,0};
	node base=a;
	while(b)
	{
		if(b&1)
		ans=mul(ans,base);
		base=mul(base,base);
		b>>=1;
	}
	return ans;
}
node cip()
{
	n%=p;
	if(n==0)
	return (node){0,0};
	if(qpow(n,(p-1)>>1)==p-1)
	return (node){-1,0};
	while(1)
	{
		a=rand()%p;
		w=((a*a%p-n)%p+p)%p;
		if(qpow(w,(p-1)>>1)==p-1)
		break;
	}
	return qmul((node){a,1},(p+1)>>1);
}
int main()
{
	ll t;
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld%lld",&n,&p);
	 	node ans=cip();
		if(ans.x==-1)
		puts("Hola!");
		else if(ans.x==0)
		puts("0");
		else if(ans.x==p-ans.x)
		printf("%lld\n",ans.x);
		else
		printf("%lld %lld\n",min(ans.x,p-ans.x),max(ans.x,p-ans.x));
	}
}