求解方程，x^2=n (mod P)。
解二次同余方程的步骤：
1、首先判断勒让德符号(n,p)是否的等于1，即n^((p-1/2)=1 (mod p)是否成立。不成立显然无解。（略）
2、任取0-(p-1)中的一a值，判断w=a*a-n是否是P的二次同余，直到找到一个否定的答案即可。（大约有一半是否定答案）
3、根据找到的w，(a+sqrt(w))^((p+1)/2)就是二次同余的解，同时最多只有两解，且两数之和为P。（要用到二次域，囧rz）
中间有一定量的推导过程，但是不是很难，琢磨琢磨吧。
对于这个题目，注意一种特殊情况，p=2时，直接输出1即可。
召唤代码君：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;int a,w;
int T,n,p,A0,B0;struct twice{
int A,B;
twice() { }
twice(int AA,int BB) { A=AA,B=BB; }
twice operator * ( twice T ) const {
A0=A*T.A+(B*T.B)%p*w;
B0=A*T.B+B*T.A;
return twice(A0%p,B0%p);
}
};int power(int A,int B)
{
int C=;
while (B){
if (B&) C=C*A%p;
A=A*A%p,B>>=;
}
return C;
}twice power(twice A,int B)
{
twice C(,);
while (B){
if (B&) C=C*A;
A=A*A,B>>=;
}
return C;
}bool lgd(int A,int B)
{
return power(A,(B-)/)==;
}int main()
{
scanf("%d",&T);
while (T--){
scanf("%d%d",&n,&p);
if (p==){
puts("");
continue;
}
if (!lgd(n,p)){
puts("No root");
continue;
}
for (;;){
a=rand()%p;
w=((a*a-n)%p+p)%p;
if (!lgd(w,p)) break;
}
twice T(a,);
T=power(T,(p+)/);
int ans1=(int)T.A,ans2=(int)p-T.A;
if (ans1>ans2) swap(ans1,ans2);
printf("%d %d\n",ans1,ans2);
}
return ;
}
