转载自：https://www.cnblogs.com/MashiroSky/p/5918158.html
先看一道poj上的题目：【poj1006】 Biorhythms
题意：
人自出生起就有体力，情感和智力三个生理周期，分别为23，28和33天。一个周期内有一天为峰值，在这一天，人在对应的方面（体力，情感或智力）表现最好。通常这三个周期的峰值不会是同一天。现在给出三个日期，分别对应于体力，情感，智力出现峰值的日期。然后再给出一个起始日期，要求从这一天开始，算出最少再过多少天后三个峰值同时出现。
分析：
首先我们要知道，任意两个峰值之间一定相距整数倍的周期。假设一年的第N天达到峰值，则下次达到峰值的时间为N+TkN+Tk(TT是周期，kk是任意正整数)。所以，三个峰值同时出现的那一天(S)(S)应满足
N1,N2,N3N1,N2,N3分别为为体力，情感，智力出现峰值的日期， T1，T2,T3T1，T2,T3分别为体力，情感，智力周期。 我们需要求出k1,k2,k3k1,k2,k3三个非负整数使上面的等式成立。
想直接求出k1,k2,k3k1,k2,k3貌似很难，但是我们的目的是求出SS， 可以考虑从结果逆推。根据上面的等式，SS满足三个要求：除以T1T1余数为N1N1，除以T2T2余数为N2N2，除以T3T3余数为N3N3。这样我们就把问题转化为求一个最小数，该数除以T1T1余N1N1，除以T2T2余N2N2，除以T3T3余N3N3。这就是著名的中国剩余定理，我们的老祖宗在几千年前已经对这个问题想出了一个精妙的解法。依据此解法的算法，时间复杂度可达到O(1)O(1)。
中国剩余定理
在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二（除以3余2），五五数之剩三（除以5余3），七七数之剩二（除以7余2），问物几何？”这个问题称为“孙子问题”，该问题的一般解法国际上称为“中国剩余定理”。具体解法分三步：
- 找出三个数：从3和5的公倍数中找出被7除余1的最小数15，从3和7的公倍数中找出被5除余1 的最小数21，最后从5和7的公倍数中找出除3余1的最小数70。
- 用15乘以2（2为最终结果除以7的余数），用21乘以3（3为最终结果除以5的余数），同理，用70乘以2（2为最终结果除以3的余数），然后把三个乘积相加15∗2+21∗3+70∗215∗2+21∗3+70∗2得到和233。
- 用233除以3，5，7三个数的最小公倍数105，得到余数23，即233%105=23233%105=23。这个余数23就是符合条件的最小数。
就这么简单。我们在感叹神奇的同时不禁想知道古人是如何想到这个方法的，有什么基本的数学依据吗？
我们将“孙子问题”拆分成几个简单的小问题，从零开始，试图揣测古人是如何推导出这个解法的。
首先，我们假设n1n1是满足除以3余2的一个数，比如2，5，8等等，也就是满足3∗k+2（k>=0）3∗k+2（k>=0）的一个任意数。同样，我们假设n2n2是满足除以5余3的一个数，n3n3是满足除以7余2的一个数。
有了前面的假设，我们先从n1n1这个角度出发，已知n1n1满足除以3余2，能不能使得n1+n2n1+n2的和仍然满足除以3余2？进而使得n1+n2+n3n1+n2+n3的和仍然满足除以3余2？
这就牵涉到一个最基本数学定理，如果有a%b=ca%b=c，则有(a+k∗b)%b=c(k为非零整数)(a+k∗b)%b=c(k为非零整数)，换句话说，如果一个除法运算的余数为cc，那么被除数与kk倍的除数相加（或相减）的和（差）再与除数相除，余数不变。这个是很好证明的。
以此定理为依据，如果n2n2是3的倍数，n1+n2n1+n2就依然满足除以3余2。同理，如果n3n3也是3的倍数，那么n1+n2+n3n1+n2+n3的和就满足除以3余2。这是从n1n1的角度考虑的，再从n2n2，n3n3的角度出发，我们可推导出以下三点：
- 为使n1+n2+n3n1+n2+n3的和满足除以3余2，n2n2和n3n3必须是3的倍数。
- 为使n1+n2+n3n1+n2+n3的和满足除以5余3，n1n1和n3n3必须是5的倍数。
- 为使n1+n2+n3n1+n2+n3的和满足除以7余2，n1n1和n2n2必须是7的倍数。
因此，为使n1+n2+n3n1+n2+n3的和作为“孙子问题”的一个最终解，需满足：
- n1n1除以3余2，且是5和7的公倍数。
- n2n2除以5余3，且是3和7的公倍数。
- n3n3除以7余2，且是3和5的公倍数。
所以，孙子问题解法的本质是从5和7的公倍数中找一个除以3余2的数n1n1，从3和7的公倍数中找一个除以5余3的数n2n2，从3和5的公倍数中找一个除以7余2的数n3n3，再将三个数相加得到解。在求n1n1，n2n2，n3n3时又用了一个小技巧，以n1n1为例，并非从5和7的公倍数中直接找一个除以3余2的数，而是先找一个除以3余1的数，再乘以2。也就是先求出5和7的公倍数模3下的逆元，再用逆元去乘余数。
这里又有一个数学公式，如果a%b=ca%b=c，那么(a∗k)%b=a%b+a%b+…+a%b=c+c+…+c=k∗c(k>0)(a∗k)%b=a%b+a%b+…+a%b=c+c+…+c=k∗c(k>0),也就是说，如果一个除法的余数为cc，那么被除数的kk倍与除数相除的余数为k∗ck∗c。展开式中已证明。
最后，我们还要清楚一点，n1+n2+n3n1+n2+n3只是问题的一个解，并不是最小的解。如何得到最小解？我们只需要从中最大限度的减掉掉3，5，7的公倍数105即可。道理就是前面讲过的定理“如果a%b=ca%b=c，则有(a−k∗b)%b=c(a−k∗b)%b=c”。所以（n1+n2+n3）%105（n1+n2+n3）%105就是最终的最小解。
这样一来就得到了中国剩余定理的公式：
设正整数
两两互素，则同余方程组
有整数解。并且在模
下的解是唯一的，解为
其中
，而
为
模
的逆元。
题目
x%ai = ri
X%5=3
X%7=4
X%9=2
X%10=1
求x
题意：有一个数x，,给出n对ai和ri，问x的最小非负整数是什么，如果不存在输出-1
这道题需要用到扩展欧几里德算法合并模线性方程组。由于这个题中所有的ai之间不一定能够保证两两互质，因而不满足中国剩余定理的条件，只能用扩展欧几里德算法对模线性方程组进行+合并。之前看网上讲了一堆关于合并模线性方程组的文章，但是还是有些不太懂。现在算是明白其中的道理。
Ax+by=c
X%a1=r1
X=x0+ k*lcm(a1,a2)
X%lcm(a1,a2)=x0
(x+k*lcm(a1,a2))%a1=r1
假设x%a1=r1,x%a2=r2。那么我们将式子写开就变成了x=k1*a1+r1,x=k2*a2+r2。所以联立两个式子就可以得到k1*a1+r1=k2*a2+r2。那么移项可得a1*k1-a2*k2=(r2-r1)。得到这个式子后我们就可以利用扩展欧几里德算法求出k1,k2的值。这里要保证k1为正数。当k1为负数时，k1不断的加上a2/gcd(a1,a2)，k2同时就要减去a1/gcd(a1,a2)。求出正数的k1以后，就可以计算出x的值。这里先暂时记作x0。我们知道这属于不定方程，所以x满足这两个模线性方程，x0+k*a1也满足两个模线性方程组，x0+k*a2也满足两个模线性方程。所以满足这两个模线性方程的x的通解为x=x0+ lcm(a1,a2)。lcm(a1,a2)是a1和a2的最小公倍数。我们将这个式子再次转换成模线性方程即得x%lcm(a1,a2)=x0。这样就可以逐步迭代求出最终满足条件的x值。
当然这是不满足中国剩余定理的情况下对模线性方程组的合并。如果满足中国剩余定理即可根据中国剩余定理来合并。不过两种不同情形下对模线性方程组的合并，实质是一样的。
还有需要说明的是扩展欧几里德算法中，出现ax-by=c（a,b,c均大于0）的情形。这不满足扩展欧几里德中的条件。因为这里我们需要求a和-b的gcd。这是不行的。因为扩展欧几里德算法说a和b必须满足a,b是不同时为0的非负数。所以我们适当变形。将上面的式子变为ax+b*(-y)=c。这样就可以正常计算了。而c的正负实际上只会影响到x，y的值。所以这样给y多加一个负号，到时候计算出结果时再将y的负号加上即可。
这道题属于合并模线性方程组的一个类型。下面附上中国剩余定理对于合并模线性方程组的描述。
下面摘自百度百科，感觉还是很重要的。
用现代数学的语言来说明的话，中国剩余定理给出了以下的一元线性同余方程组：
有解的判定条件，并用构造法给出了在有解情况下解的具体形式。
中国剩余定理说明：假设整数m1,m2, ... ,mn两两互质，则对任意的整数：a1,a2, ... ,an，方程组有解，并且通解可以用如下方式构造得到：
设是整数m1,m2, ... ,mn的乘积，并设是除了mi以外的n- 1个整数的乘积。
设为模的数论倒数：
方程组的通解形式为：在模的意义下，方程组只有一个解：
中国剩余定理还是很重要的，比如对一个数取模，而这个数可以分解成几个互质的数，那么我们就可以分别对这几个互质的数进行取模，然后再用中国剩余定理合并。比较难的题中中国剩余定理也会与矩阵快速幂等知识点相结合。比如HDU 4767等。
参考代码：