推論1：方程ax=b(mod n)對于未知量x有解，當(dāng)且僅當(dāng)gcd(a,n) | b。
推論2：方程ax=b(mod n)或者對模n有d個不同的解，其中d=gcd(a,n)，或者無解。
定理1：設(shè)d=gcd(a,n)，假定對整數(shù)x和y滿足d=ax+by(比如用擴展Euclid算法求出的一組解)。如果d | b，則方程ax=b(mod n)有一個解x0滿足x0=x*(b/d) mod n 。特別的設(shè)e=x0+n，方程ax=b(mod n)的最小整數(shù)解x1=e mod (n/d)，最大整數(shù)解x2=x1+(d-1)*(n/d)。
定理2：假設(shè)方程ax=b(mod n)有解，且x0是方程的任意一個解，則該方程對模n恰有d個不同的解(d=gcd(a,n))，分別為：xi=x0+i*(n/d) mod n 。
證明過程請詳見 《算法導(dǎo)論》
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
int EXTENDED_EUCLID(int a,int b,int &x,int &y)//擴展歐幾里德算法
{
if(b==0)
{
x=1;
y=0;
return a;
}
int r=EXTENDED_EUCLID(b,a%b,x,y);
int temp=x;
x=y;
y=temp-a/b*y;
return r;
}
int MODULAR_LINEAR(int a,int b,int n)//求解模線性方程
{
int d,x,y;
int x0;
d=EXTENDED_EUCLID(a,n,x,y);
x0=(x*(b/d)+n)%n;
return x0;
}
//當(dāng)時魚頭讓我們研究的時候，沒有考慮得太仔細(xì)，上面的方程只能求出一個可行解
//而下面的函數(shù)能夠求出最小的整數(shù)解，甚至在模n內(nèi)任意的解
long long MODULAR_LINEAR(long long a,long long b,long long n)//求解模線性方程
{
long long d,x,y;
long long x0;
d=EXTENDED_EUCLID(a,n,x,y);
if(b%d)
return -1;
x0=(x*(b/d))%n+n;//確保是正數(shù)
x0%=(n/d);//x0是第一個大于0的整數(shù)解
return x0;
}
int CHINESE_RESIDUE_THEOREM(int n[],int b[],int k)//求解模線性方程組，所有數(shù)據(jù)從1號下標(biāo)開始存儲
{
int result=0;
int i;
int N=1;
int *m=new int [k+1];
int *reversem=new int [k+1];
int sum=0;
for(i=1;i<=k;i++)
{
N*=n[i];
}
for(i=1;i<=k;i++)
{
m[i]=N/n[i];
reversem[i]=MODULAR_LINEAR(m[i],1,n[i]);
sum+=m[i]*reversem[i]*b[i];
}
result=sum%N;
return result;
}
int main ()
{
int num;
int i;
printf("參考格式:X mod n[i] = b[i]\n");
cout<<"請輸入方程的個數(shù)：";
cin>>num;
int *n=new int [num+1];
int *b=new int [num+1];
for(i=1;i<=num;i++)
{
cout<<"請輸入第"<<i<<"個方程的n和b:";
cin>>n[i]>>b[i];
}
int result=CHINESE_RESIDUE_THEOREM(n,b,num);
cout<<"解為:";
cout<<result<<endl;
cout<<"謝謝你的使用"<<endl;
system("pause");
return 0;
}