用数学化的符号表示就是求解a_i×x≡b_i(mod m_i)(1<=i<=n)这样的方程。如果方程有解，那么一定有无穷多解，而且解的全集一定可以写成x≡b(mod m)的形式，因此问题就转化为求解b和m。如果我们能求解方程组x≡b₁(mod m₁),a×x≡b₂(mod m₂),那么只需要对方程逐个求解，对于任意有限的n我们就都可以求出答案了。

下面我们来推倒一下如何求方程的解：

因为x≡b₁(mod m₁)所以不能想到可以把x写成x=b₁+m₁×t的形式。把它带入第二条式子，可以得到a(b₁+m₁×t)≡b₂(mod m₂)移项整理后得到a×m₁×t≡b₂-a×b₁(mod m₂)由于这只是一个一次同余方程，因此很容易求解。其中当gcd(m₂,a×m₁)无法整除b₂-a×b₁时原方程组无解。在求t的过程中我们需要用到(int mod_inverse(int,int))，int gcd(int,int)是

1 int n; 2 int x=0,m=1; 3 int A[MAXN],B[MAXN],M[MAXN]; 4 void linear_congruence(){ 5     for(int i=1;i<=n;i++){ 6         int a=A[i]*m,b=B[i]-A[i]*x,d=gcd(M[i],a); 7         if(b%d!=0){ 8             x=0;m=-1; 9             return;10         }11         int t=b/d*mod_inverse(a/d,M[i]/d)%(M[i]%d)12         x=x+m*t;13         m*=M[i]/d;14     }15     return;16 }