下面代码实现就是二次剩余里的一个结论。
懒人的话记住结论就行。。
在[0,p-1]中随机挑选一个数a，定义,若：,那么就是一组二次剩余。
期望2次就能找到结果。。
这里涉及到根号次幂运算，我们用复数类运算来模拟。
把虚数平方I的值设置为W，那么虚数的单位1就是了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;int mod;
ll I_mul_I; // 虚数单位的平方struct cpx {ll real, imag;cpx(ll real = 0, ll imag = 0): real(real), imag(imag) { }
};
inline bool operator == (cpx x, cpx y) {return x.real == y.real and x.imag == y.imag;
}
inline cpx operator * (cpx x, cpx y) {return cpx((x.real * y.real + I_mul_I * x.imag % mod * y.imag) % mod,(x.imag * y.real + x.real * y.imag) % mod);
}//虚数除法可以转化为乘法来做，加减法直接实虚部相加减即可 cpx power(cpx x, int k) {cpx res = 1;while(k) {if(k & 1) res = res * x;x = x * x;k >>= 1;}return res;
}bool check_if_residue(int x) {return power(x, (mod - 1) >> 1) == 1;
}void solve(int n, int p, int &x0, int &x1) {mod = p;ll a = rand() % mod;while(!a or check_if_residue((a * a + mod - n) % mod))a = rand() % mod;I_mul_I = (a * a + mod - n) % mod;//这里虚部单位是sqrt(w)，I^2 = w x0 = power(cpx(a, 1), (mod + 1) >> 1).real;//(a+sqrt(w))^ { (p+1)/2 } 用复数来实现根号运算 x1 = mod - x0;
}
int main()
{int t;srand(time(0));scanf("%d",&t);while(t--){int n;scanf("%d%d",&n,&mod);if(n==0)puts("0");else if(!check_if_residue(n))printf("Hola!\n");else{int x1,x2;solve(n,mod,x1,x2);if(x1>x2)swap(x1,x2);if(x1==x2)printf("%d\n",x1);else printf("%d %d\n",x1,x2);}}return 0;}