按照惯例先%mmh 例题：P5491 【模板】二次剩余 题目背景 模板题，无背景。
题目描述 求解方程 x2≡N(mod p)
多组数据。
保证p是奇素数
输入格式 第一行一个整数T表示数据组数。
接下来T行，每行一个N一个p。
输出格式 输出共T行。
对于每一行输出：
若有解，则按mod p后递增的顺序输出在mod p意义下的全部解.
若两解相同，只输出其中一个；
若无解，则输出Hola!；
输入输出样例 输入 #1 复制 3 5 1000000009 4 1000000009 0 19260817 输出 #1 复制 383008016 616991993 2 1000000007 0 说明/提示 T≤10000 N,p≤1e9+9
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<vector> #include<cmath> #define ll long long #define llu unsigned ll using namespace std; const int inf=0x3f3f3f3f; const ll lnf=0x3f3f3f3f3f3f3f3f; struct node { ll x,y; node(){} node(ll a,ll b) { x=a,y=b; } }; node mul(const node &a,const node &b,const ll &w,const ll &p) { node ans; ans.x=((a.x*b.x%p+a.y*b.y%p*w%p)%p+p)%p; ans.y=((a.x*b.y%p+a.y*b.x%p)+p)%p; return ans; } ll mypow(ll a,ll b,ll p) { ll ans=1; while(b) { if(b&1) ans=ans*a%p; a=a*a%p; b>>=1; } return ans; } ll mypow(node a,ll b,ll w,ll p) { node ans=node(1,0); while(b) { if(b&1) ans=mul(ans,a,w,p); a=mul(a,a,w,p); b>>=1; } return ans.x%p; } ll fi(ll n,ll p) { n%=p; if(p==2) return n; if(mypow(n,(p-1)/2,p)==p-1) return -1; ll a,w; while(1) { a=rand()%p; w=((a*a%p-n)%p+p)%p; if(mypow(w,(p-1)/2,p)==p-1) break; } node ans=node(a,1); return mypow(ans,(p+1)/2,w,p); } int main(void) { int t; scanf("%d",&t); while(t--) { ll n,p; scanf("%lld%lld",&n,&p); if(n==0) { printf("0\n"); } else { ll ans1=fi(n,p); if(ans1==-1) printf("Hola!\n"); else { ll ans2=p-ans1; if(ans1>ans2) swap(ans1,ans2); printf("%lld %lld\n",ans1,ans2); } } } return 0; }