解同余式组（孙子定理）

/*这是对孙子定理的同余式的解法实现，先选择有几个同余式 再输入(ax=b(modc))中的a,b,c， 输入一个同余式是求x，输入多个就是求同余式组了。 利用二维表作为存储数据的地方 0-2存a,b,c 3-12存算出的根 13记录根的个数 14存合适的M值 测试数据： 一个式子:2x=179(mod 562) 179不能整除Gcd(2,562) 一个式子:256x=179(mod 337) 解为:81 一个式子:1215x=560(mod 2755) 解为:200 751 1302 1853 2404 一个式子:1296x=1125(mod 1935) 解为:80 295 510 725 940 1155 1370 1585 1800 同余式组:x=1(mod 7) x=1(mod 8) x=3(mod 9) 解为:x=57+504*k (k=1,2,3,4 . . .) 同余式组:x=1(mod 2) x=2(mod 5) x=3(mod 7) x=4(mod 9) 解为: x=157+630*k (k=1,2,3,4 . . .) 同余式组:x=1(mod 7) 3x=4(mod 5) 8=4(mod 9) 解为: x=113+315*k (k=1,2,3,4 . . .) */ /*此源码为交流思想为主，如要考虑非法输入的情况，请自行添加判断*/ #include <iostream> #include <conio.h> //控制getch的,无大作用 struct triple { int d,x,y; }; int mod(int a,int b); //求模运算 triple Extended_Euclid(int a,int b); //扩展的欧几里得算法 int MLES(int a,int b,int n); //求解ax=b(mod n) int Gcd(int a,int b); //求最大公约数 int Lcm(int a,int b); //求最小公倍数 void Print(); int a[10][15]={0}; //二维表 int n,lcm,num,tem=0; //n存储几个式子,lcm存最小公倍数，num存同余式组的最小解， using namespace std; int main() { int i,j,m=0; //m存最大公约数 cout<<"一共有几个式子？(最多十个):"; cin>>n; for(i=0;i<n;i++) { cout<<"依次输入ax=b(mod c)中的a b c："; cin>>a[i][0]>>a[i][1]>>a[i][2]; } for(i=0;i<n;i++) //计算 { a[i][13]=Gcd(a[i][0],a[i][2]); if ((a[i][1]%a[i][13])==0) { a[i][3]=MLES(a[i][0]/a[i][13],a[i][1]/a[i][13],a[i][2]/a[i][13]); if (a[i][13]>1) { lcm=Lcm(a[i][0],a[i][2]); for (j=4;j<3+a[i][13];j++) { a[i][j]=a[i][j-1]+a[i][2]/a[i][13]; } } } else { cout<<"第"<<i+1<<"个式子无解!"<<endl; return 0; } } if (n==1) { Print(); } else { lcm=a[0][2]; for (i=1;i<n;i++) { lcm=Lcm(lcm,a[i][2]); } cout<<lcm<<endl; for (i=0;i<n;i++) { for (j=1;;j++) { a[i][14]=lcm/a[i][2]*j; if (a[i][14]%a[i][2]==1) break; } } for (i=0;i<n;i++) { tem+=a[i][3]*a[i][14]; } num=tem%lcm; Print(); } getch(); return 0; } int Gcd(int a,int b) { if(b == 0) return a; else return Gcd(b,mod(a,b)); } int MLES(int a,int b,int n) { triple ee = Extended_Euclid(a,n); if(mod(b,ee.d) == 0) return mod((ee.x * (b / ee.d)),n / ee.d); else return -1; } int mod(int a,int b) { if(a >= 0) return a % b; else return a % b + b; } int Lcm(int a,int b) { return a*b/Gcd(a,b); } triple Extended_Euclid(int a,int b) { triple result; if(b == 0) { result.d = a; result.x = 1; result.y = 0; } else { triple ee = Extended_Euclid(b,mod(a,b)); result.d = ee.d; result.x = ee.y; result.y = ee.x - (a/b)*ee.y; } return result; } void Print() { if(n==1) { for (int j=3;j<3+a[0][13];j++) { cout<<a[0][j]<<" "; } cout<<endl; } else { cout<<"此题的解为: x="<<num<<"+"<<lcm<<"*k (k=1,2,3,4 . . .)"<<endl; } /* 查看二维表 for (int i=0;i<10;i++) { for (int j=0;j<15;j++) { cout<<a[i][j]<<" "; } cout<<endl; }*/ }