中国剩余定理模板（互质与非互质）

互质模板

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int Extended_Euclid(int a,int b,int &x,int &y)    //扩展欧几里得算法
 5 {
 6     int d;
 7     if(b==0)
 8     {
 9         x=1;y=0;
10         return a;
11     }
12     d=Extended_Euclid(b,a%b,y,x);
13     y-=a/b*x;
14     return d;
15 }
16 
17 int Chinese_Remainder(int a[],int w[],int len)    //中国剩余定理  a[]存放余数  w[]存放两两互质的数
18 {
19     int i,d,x,y,m,n,ret;
20     ret=0;
21     n=1;
22     for (i=0;i<len;i++)
23         n*=w[i];
24     for (i=0;i<len;i++)
25     {
26         m=n/w[i];
27         d=Extended_Euclid(w[i],m,x,y);
28         ret=(ret+y*m*a[i])%n;
29     }
30     return (n+ret%n)%n;
31 }
32 
33 
34 int main()
35 {
36     int n,i;
37     int w[15],b[15];
38     while (scanf("%d",&n),n)   
39     {
40         for (i=0;i<n;i++)
41         {
42             scanf("%d%d",&w[i],&b[i]);
43         }
44         printf("%d/n",Chinese_Remainder(b,w,n));
45     }
46     return 0;
47 }

View Code

非互质模板

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 #define LL long long
 8 const LL maxn=100000+10;
 9 LL a[maxn],b[maxn];
10 //拓展欧几里得定理，求ax+by=gcd(a,b)的一组解(x,y),d=gcd(a,b)
11 void gcd(LL a,LL b,LL &d,LL &x,LL &y)
12 {
13     if(!b){d=a;x=1;y=0;}
14     else{gcd(b,a%b,d,y,x);y-=x*(a/b);}
15 }
16 LL china(LL n,LL a[],LL b[])
17 {
18     LL m1,r1,m2,r2,flag=0,i,d,x,y,c,t;
19     m1=a[0],r1=b[0];
20     flag=0;
21     for(i=1;i<n;i++)
22     {
23         m2=a[i],r2=b[i];
24         if(flag)continue;
25         gcd(m1,m2,d,x,y);//d=gcd(m1,m2);x*m1+y*m2=d;
26         c=r2-r1;
27         if(c%d)//对于方程m1*x+m2*y=c，如果c不是d的倍数就无整数解
28         {
29             flag=1;
30             continue;
31         }
32         t=m2/d;//对于方程m1x+m2y=c=r2-r1,若(x0,y0)是一组整数解,那么(x0+k*m2/d,y0-k*m1/d)也是一组整数解(k为任意整数)
33         //其中x0=x*c/d,y0=x*c/d;
34         x=(c/d*x%t+t)%t;//保证x0是正数，因为x+k*t是解，(x%t+t)%t也必定是正数解(必定存在某个k使得(x%t+t)%t=x+k*t)
35         r1=m1*x+r1;//新求的r1就是前i组的解，Mi=m1*x+M(i-1)=r2-m2*y(m1为前i个m的最小公倍数);对m2取余时，余数为r2；
36         //对以前的m取余时，Mi%m=m1*x%m+M(i-1)%m=M(i-1)%m=r
37         m1=m1*m2/d;
38     }
39     if(flag)return -1;
40     if(n==1&&r1==0)return m1;//结果不能为0
41     return r1;
42 }
43 
44 int main()
45 {
46     LL i,n,tt=0;
47     
48         cin>>n;
49         for(i=0;i<n;i++)
50             cin>>a[i]>>b[i];
51         cout<<china(n,a,b)<<endl;
52     
53     return 0;
54 }
55 /*
56  中国剩余定理(不互质形式)模板题。
57  注意只有一组且剩余数为0的时候。结果不能为0
58  */

View Code