自从昨天开始，老子就一直在看中国剩余定理，硬是搞不懂。后来问了安叔多个问题，才逐渐明白了过来。
先说同余方程组的求解吧！
同于方程组是以组形如
x=a1 (mod m1)
x=a2 (mod m2)
x=a3 (mod m3)
........................
x=an (mod mn)
等多个一组的这样的方程。
解这样的方程组，有两个典型的解法。
第一就是中国剩余定理：这个定理可以快速地解出所求的X，但是也有一个明显的缺陷。中哦过剩余定理的使用前提是m1,m2.......mn两两互素。正是由此，这个定理的使用范围有所限定。于是就有了第二个定理、
第二就是用合并方程组的形式来求解同余方程组。对于x=a1 (mod m1)=a2 (mod m2)，设（y0,z0）这两个方程组成的方程组的一个解。这是就可以把这两个方程合并为x=(a1+y0*m1) mod (lcm(m1,m2))。这个合并时可以被证明的，具体证明在安叔的课件上有详细的讲解。
有了这两个方法（尤其是第二个），咱们对于一般的求同余方程的水体就可以ko掉了。
下面来一发水题，以示我学过了同余方程组的求解。
题目编号为：POJ1177
如下
Description
Elina is reading a book written by Rujia Liu, which introduces a strange way to express non-negative integers. The way is described as following:
Choose k different positive integers a1, a2, …, ak. For some non-negative m, divide it by every ai (1 ≤ i ≤ k) to find the remainder ri. If a1, a2, …, ak are properly chosen, m can be determined, then the pairs (ai, ri) can be used to express m.
“It is easy to calculate the pairs from m, ” said Elina. “But how can I find m from the pairs?”
Since Elina is new to programming, this problem is too difficult for her. Can you help her?
Output
Output the non-negative integer m on a separate line for each test case. If there are multiple possible values, output the smallest one. If there are no possible values, output -1.
Hint
All integers in the input and the output are non-negative and can be represented by 64-bit integral types.
Source
题目的解法就是上面的说的合并方程组（不能用中国剩余定理，因为无法判断解是否存在的情况）
代码：
＃i nclude <iostream>
＃i nclude <cstdio>
#define ll long long
#define maxn 10001
using namespace std;
ll c[maxn],m[maxn],n,am,ac,y0,z0,d;
bool ans;
void exgcd(ll a,ll b,ll& d,ll& x,ll& y)
{
if (b==0) { d=a,x=1,y=0; }
else { exgcd(b,a%b,d,y,x); y-=x*(a/b); }
}
int main()
{
ll i;
while (scanf("%I64d",&n)!=EOF)
{
ans=true;
for (i=1; i<=n; i++) scanf("%I64d%I64d",&m[i],&c[i]);
am=m[1];
ac=c[1];
for (i=2; i<=n; i++)
{
exgcd(am,m[i],d,y0,z0);
if ((ac-c[i])%d!=0)
{
ans=false;
break;
}
y0=(c[i]-ac)/d*y0;
y0=((y0%(m[i]/d))+(m[i]/d))%(m[i]/d);
ac=am*y0+ac,am=am/d*m[i],ac=(ac%am+am)%am;
}
if (ans) printf("%I64d\n",ac);
else printf("-1\n");
}
return 0;
}
0.0
