数论之二次剩余

时间：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 }

tql

还有牛客多校的一题：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

 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 }

tqlll

剩下的合数的还有其他补充内容就之后再更。

原文：https://www.cnblogs.com/LMCC1108/p/11365068.html