传送门
MD写一道二次剩余的板题差点写自闭了。
我用的是cipollacipollacipolla算法。
利用的是欧拉准则来找寻一个二次非剩余类来求根。
注意这题有两个等根和模数为2的情况。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,mod;
inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=(ll)a*a%mod)if(p&1)ret=(ll)ret*a%mod;return ret;}
namespace find_root{
int w=0,a,b;
inline bool check(int v){return ::ksm(w=((ll)v*v%mod-a+mod)%mod,(mod-1)/2)!=1;}
struct Complex{
int x,y;
friend inline Complex operator*(const Complex&a,const Complex&b){return (Complex){((ll)a.x*b.x%mod+(ll)a.y*b.y%mod*w%mod)%mod,((ll)a.x*b.y%mod+(ll)a.y*b.x%mod)%mod};}
friend inline int ksm(Complex a,int p){Complex ret=(Complex){1,0};for(;p;p>>=1,a=a*a)if(p&1)ret=ret*a;return ret.x;}
};
inline int calc(int k){
a=k;
if(ksm(a,(mod-1)/2)^1)return -1;
while(!check(b=rand()));
return ksm((Complex){b,1},(mod+1)/2);
}
}
int main(){
srand(time(NULL));
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&mod);
n%=mod;
if(mod==2){puts("1");continue;}
if(mod==1){puts("No root");continue;}
int ans=find_root::calc(n);
if(ans>0){
if(ans*2==mod)printf("%d\n",ans);
else printf("%d %d\n",min(ans,mod-ans),max(ans,mod-ans));
}
else puts("No root");
}
return 0;
}