class="markdown_views prism-tomorrow-night">

传送门

---

解析：

这道题由于模数一定是质数，所以我们只需要特判掉模数为2的情况，剩下的就是模奇质数二次剩余了。 关于二次剩余可以看我的博客

---

代码： #include using namespace std; #define ll long long #define re register #define gc getchar #define pc putchar #define cs const #define complex COMPLEX namespace IO{ inline int getint(){ re int num; re char c; while(!isdigit(c=gc()));num=c^48; while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48); return num; } inline void outint(ll a){ static char ch[23]; if(a==0)pc('0'); while(a)ch[++ch[0]]=a-a/10*10,a/=10; while(ch[0])pc(ch[ch[0]--]^48); } } using namespace IO; inline ll mul(cs ll &a,cs ll &b,cs ll &mod){ return (a*b-(ll)((long double)a/mod*b)*mod+mod)%mod; } struct complex{ ll x,y; complex():x(1),y(0){} complex(ll _x,ll _y):x(_x),y(_y){} }; ll W,mod; complex operator*(cs complex &a,cs complex &b){ return complex((mul(a.x,b.x,mod)+mul(mul(a.y,b.y,mod),W,mod))%mod,(mul(a.x,b.y,mod)+mul(a.y,b.x,mod))%mod); } inline ll quickpow(ll a,ll b){ ll ans=1; for(;b;b>>=1,a=mul(a,a,mod))if(b&1)ans=mul(ans,a,mod); return ans; } inline complex quickpow(complex a,ll b){ complex res; for(;b;b>>=1,a=a*a)if(b&1)res=res*a; return res; } inline ll solve(ll a){ if(mod==2)return 1; if(quickpow(a,(mod-1)>>1)==mod-1)return -1; re ll b; while(true){ b=rand()%mod; W=(mul(b,b,mod)-a+mod)%mod; if(quickpow(W,(mod-1)>>1)==mod-1)break; } return quickpow(complex(b,1),(mod+1)>>1).x; } int T;ll a; signed main(){ T=getint(); srand(time(0)); while(T--){ a=getint();mod=getint(); a%=mod; a=solve(a); if(~a){ re ll b=mod-a; if(a>b)swap(a,b); if(a^b)outint(a),pc(' '),outint(b),pc(' '); else outint(a),pc(' '); } else puts("No root"); } return 0; }