直接来一个裸题：http://acm.timus.ru/problem.aspx?space=1&num=1132
1 #include<cstdio> 2 #include<cstdlib> 3 #include<ctime> 4 struct Ima{ 5 int x,y; 6 }; 7 int p,w; 8 Ima muli(const Ima &i1,const Ima &i2){ 9 Ima ans; 10 ans.x=(i1.x*i2.x%p+i1.y*i2.y%p*w%p)%p; 11 ans.y=(i1.x*i2.y%p+i1.y*i2.x%p)%p; 12 return ans; 13 } 14 Ima powi(Ima a,int b){ 15 Ima ans; 16 ans.x=1,ans.y=0; 17 while(b){ 18 if(b&1) ans=muli(ans,a); 19 a=muli(a,a); 20 b>>=1; 21 } 22 return ans; 23 } 24 int poww(int a,int b){ 25 int ans=1; 26 a%=p; 27 while(b){ 28 if(b&1) ans=ans*a%p; 29 a=a*a%p; 30 b>>=1; 31 } 32 return ans; 33 } 34 int Cipolla(int n){ 35 if(p==2) return 1; 36 if(poww(n,(p-1)>>1)+1==p) return -1; 37 int a; 38 while(true){ 39 a=rand()%p; 40 w=((a*a%p-n)%p+p)%p; 41 if(poww(w,(p-1)>>1)+1==p) break; 42 } 43 Ima ans; 44 ans.x=a,ans.y=1; 45 ans=powi(ans,(p+1)>>1); 46 return ans.x; 47 } 48 int main(){ 49 int t,n,ans1,ans2; 50 srand(time(NULL)); 51 scanf("%d",&t); 52 while(t--){ 53 scanf("%d%d",&n,&p); 54 n%=p; 55 ans1=Cipolla(n),ans2=p-ans1; 56 if(ans1==-1) printf("No root\n"); 57 else if(ans1==ans2) printf("%d\n",ans1); 58 else if(ans1<ans2) printf("%d %d\n",ans1,ans2); 59 else printf("%d %d\n",ans2,ans1); 60 } 61 return 0; 62 }
还有牛客多校的一题：Quadratic equation
1 #include<cstdio> 2 #include<cstdlib> 3 #include<ctime> 4 typedef long long ll; 5 const ll p=1e9+7; 6 struct Ima{ 7 ll x,y; 8 }; 9 ll w; 10 Ima muli(const Ima &i1,const Ima &i2){ 11 Ima ans; 12 ans.x=(i1.x*i2.x%p+i1.y*i2.y%p*w%p)%p; 13 ans.y=(i1.x*i2.y%p+i1.y*i2.x%p)%p; 14 return ans; 15 } 16 Ima powi(Ima a,ll b){ 17 Ima ans; 18 ans.x=1,ans.y=0; 19 while(b){ 20 if(b&1) ans=muli(ans,a); 21 a=muli(a,a); 22 b>>=1; 23 } 24 return ans; 25 } 26 ll poww(ll a,ll b){ 27 ll ans=1; 28 a%=p; 29 while(b){ 30 if(b&1) ans=ans*a%p; 31 a=a*a%p; 32 b>>=1; 33 } 34 return ans; 35 } 36 ll Cipolla(ll n){ 37 if(n==0) return 0; 38 if(n==1) return 1; 39 if(poww(n,(p-1)>>1)+1==p) return -1; 40 ll a; 41 while(true){ 42 a=rand()%p; 43 w=((a*a%p-n)%p+p)%p; 44 if(poww(w,(p-1)>>1)+1==p) break; 45 } 46 Ima ans; 47 ans.x=a,ans.y=1; 48 ans=powi(ans,(p+1)>>1); 49 return ans.x; 50 } 51 void solve(ll b,ll c){ 52 ll n=((b*b%p-4*c%p)%p+p)%p; 53 ll a=Cipolla(n),x,y; 54 if(a==-1){ 55 printf("-1 -1\n"); 56 return ; 57 } 58 if(!((a+b)&1)) y=(a+b)/2,x=b-y; 59 else y=(a+b+p)/2,x=b+p-y; 60 x=(x+p)%p; 61 y=(y+p)%p; 62 if(x>y) printf("%lld %lld\n",y,x); 63 else printf("%lld %lld\n",x,y); 64 } 65 int main(){ 66 int t; 67 ll b,c; 68 srand(time(NULL)); 69 scanf("%d",&t); 70 while(t--){ 71 scanf("%lld%lld",&b,&c); 72 solve(b,c); 73 } 74 return 0; 75 }
剩下的合数的还有其他补充内容就之后再更。
原文：https://www.cnblogs.com/LMCC1108/p/11365068.html
