数论之二次剩余
时间:2019-08-16 17:27:22
收藏:0
阅读:77
来自各个大佬的讲解与证明:
二次剩余Cipolla算法学习笔记 - bztMinamoto - 博客园
[数论]二次剩余及计算方法 – Miskcoo‘s Space
浅谈二次剩余 - stevensonson的博客 - CSDN博客
二次剩余入门 - Eiffel的博客 - CSDN博客
图文]第4章二次同余方程 - 百度文库
二次剩余Cipolla算法学习小记 - 待成熟的葡萄 - CSDN博客
直接来一个裸题: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
Amy asks Mr. B problem B. Please help Mr. B to solve the following problem.
Let p = 1000000007.
Given two integers b and c, please find two integers x and y(0≤x≤y<p) such that
(x+y)?mod?p=b
(x×y)?mod?p=c
由(x+y)%p=b,以及x跟y的取值范围,我们可以知道x+y只有b或者是p+b两个结果,然后(x-y)2=(x+y)2-4xy,而xy%p=c,所以可以得到(x-y)2≡b2-4c (mod p),把这个同余方程解出来就行了。

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
评论(0)