\(x^2\equiv n\pmod p\)，其中 \(p\) 是奇素数。
当 \(n=0\) 时有 \(x=0\)，以下规定 \(n\not=0\)。
假设 \(n\) 是二次剩余且有多个不同解，其中两个解分别是 \(x_0,x_1\in [1,p)\)。
有 \({x_0}^2\equiv {x_1}^2\equiv n\pmod p\)。
移项，平方差公式得 \((x_0+x_1)(x_0-x_1)\equiv 0\pmod p\)。
由于 \(x_0\not =x_1\)，所以 \((x_0+x_1)\equiv 0\pmod p\)。即 \(x_0,x_1\) 在模 \(p\) 意义下互为相反数。
所以每一对相反数对应着一个二次剩余，每一个二次剩余也只有可能对应着一对相反数。
所以在 \([1,p)\) 当中二次剩余与非二次剩余的个数都为 \(\frac{p-1}{2}\)。
根据费马小定理 \(x^{p-1}\equiv 1\pmod p\)。
若 \(n\) 是二次剩余则 \(n^{\frac{p-1}{2}}\equiv x^{p-1}\equiv 1\pmod p\)。
同时根据 \(n^{p-1}\equiv 1\pmod p\)，得 \(n^{\frac{p-1}{2}}\equiv \pm 1\pmod p\)。
所以 \(n\) 是非二次剩余则 \(n^{\frac{p-1}{2}}\equiv -1\pmod p\)。
根据这个可以判断 \(n\) 是否为二次剩余。
解方程的时候，先随便找到一个 \(a\in[1,p)\) 使 \(a^2-n\) 是非二次剩余。
由于二次剩余与非二次剩余数量相同，所以随机找期望两次就能找到。
然后定义 \(i^2\equiv a^2-n\)，这里 \(i\) 类比复数的概念。
根据二项式定理展开 \((a+i)^p\)，由于 \(p\) 是质数，所以 \((a+i)^p\equiv a^p+i^p\)。
由定义有 \(i^p\equiv i(i^2)^{\frac{p-1}{2}}\equiv i(a^2-n)^{\frac{p-1}{2}}\equiv -i\)。
所以 \((a+i)^{p+1}\equiv (a-i)(a+i)\equiv a^2-(a^2-n)\equiv n\)。
所以 \((a+i)^{\frac{p+1}{2}}\) 就是解之一，另一个是其相反数。
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
int T,n,p,a,mul,ans;
struct node
{
int r,i;
inline node operator *(node &o)
{return {(r*o.r+mul*i%p*o.i)%p,(r*o.i+i*o.r)%p};}
};
inline int ksm(node a,int b)
{
node ans={1,0};
while(b)
{
if(b&1) ans=ans*a;
a=a*a,b>>=1;
}
return ans.r;
}
inline bool Check(int x){return ksm({x,0},(p-1)/2)==1;}
signed main()
{
#ifdef ONLINE_JUDGE
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
#endif
cin>>T;
while(T--)
{
cin>>n>>p;mul=0;
if(!n){cout<<"0\n";continue;}
if(!Check(n)){cout<<"Hola!\n";continue;}
a=rand()%p;while(!a||Check((a*a-n+p)%p)) a=rand()%p;
mul=(a*a-n+p)%p;ans=ksm({a,1},(p+1)/2);
ans=min(ans,p-ans);cout<<ans<<' '<<p-ans<<'\n';
}
return 0;
}