题意：求${x^2} \equiv n\bmod p$
解题关键：
定理：若$a$满足$w = {a^2} - n$是模$p$的二次非剩余，即，${x^2} = w\bmod p$无解，则${(a + \sqrt w )^{\frac{{p + 1}}{2}}}$是二次剩余方程${x^2} \equiv n\bmod p$的解。
证明：
$\begin{array}{l}
{x^2} \equiv {(a + \sqrt w )^{p + 1}} \equiv (a + \sqrt w ){(a + \sqrt w )^p}\\
\equiv (a + \sqrt w )(\sum {C_p^i{a^{p - i}}{w^{\frac{i}{2}}}} )\\
\equiv (a + \sqrt w )({a^p} + {w^{\frac{{p - 1}}{2}}}\sqrt w )\\
\equiv (a + \sqrt w )(a - \sqrt w )\\
\equiv n(\bmod p)
\end{array}$
#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<iostream> #include<cmath> using namespace std; typedef long long ll; ll w,a,x,p,T; struct CN{ ll x,y; CN friend operator *(CN x,CN y){ CN z; z.x=(x.x*y.x+x.y*y.y*w)%p; z.y=(x.x*y.y+x.y*y.x)%p; return z; } }; CN Cmod_pow(CN x,ll n){ CN z={1,0}; while(n){ if(n&1)z=z*x; x=x*x; n>>=1; } return z; } ll mod_pow(ll x,ll n,ll p){ ll res=1; while(n){ if(n&1) res=res*x%p; x=x*x%p; n>>=1; } return res; } int main(){ scanf("%lld",&T); while(T--){ scanf("%lld%lld",&x,&p); x%=p; if(p==2){ printf("1\n"); continue; } if(mod_pow(x,(p-1)/2,p)==p-1){ printf("No root\n"); continue; } while(1){ a=rand()%p; w=(a*a-x+p)%p; if(mod_pow(w,(p-1)/2,p)==p-1) break; } CN u={a,1}; u=Cmod_pow(u,(p+1)/2); ll yi=u.x,er=p-u.x; if(yi>er) printf("%lld %lld\n",er,yi); else if(yi==er) printf("%lld\n",yi); else printf("%lld %lld\n",yi,er); } }