模线性方程组:
给定了n组除数m[i]和余数r[i]，通过这n组(m[i],r[i])求解一个z，使得z % m[i] = r[i]
首先,从最简单的情况入手,只有两条方程:
设z%m0=r0, z%m1=r1;
=>z=r0+m0*k0, z=r1+m1*k1( k1,k2 为常数 )
=>r0+m0*k0=r1+m1*k1
=>m0*k0-m1*k1=r1-r0
设m0为A,m1为B,k0为x,-k1为y,r1-r0为C,则A*x+B*y=C;
所以很容易想到,这个可以用扩展欧几里德来求
求出x后,求出z0=r0+m0*k0=r0+m0*x
同时,我们将这个z0作为特解，可以扩展出一个解系：
Z = z0 + k*lcm(m0, m1) k为整数
化为方程式可以得到Z%lcm(m0, m1)=z0;
设M=lcm(m0, m1),R=z0,所以Z%M=R;
此时，可以发现我们将z mod m0= r0，z mod m1 = r1合并为了一个式子Z mod lcm(m0, m1) = z0。满足后者的X一定满足前两个式子。
每两个式子都可以通过该方法化简为一个式子。那么我们只要重复进行这个操作，就可以将n个方程组化简为一个方程，并且求出一个最后的解了。
模板:
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAXN=15;
typedef long long LL;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
LL res=exgcd(b,a%b,x,y);
LL tmp=x;
x=y;
y=tmp-a/b*y;
return res;
}
LL solve(LL m[MAXN],LL r[MAXN],int n)
{
LL x,y;
LL M=m[0],R=r[0],C,gcd;
for(int i=1;i<n;i++)
{
gcd=exgcd(M,m[i],x,y);
C=r[i]-R;
if(C%gcd!=0) return -1;
x=(x/gcd*C)%(m[i]/gcd);//x*C/gcd为方程的初解x0,x0%(m[i]/gcd)为最小的正整数解,避免溢出
R=M*x+R;//z = m[i] * k[i] + r[i]
M=M*m[i]/gcd;//求出最小公倍数 lcm(M,m[i])
R%=M;// 求解合并后的新R，同时让R最小
}
if(R<0)
{
R+=M;
}
return R;
}
LL m[MAXN],r[MAXN];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
{
scanf("%lld%lld",m+i,r+i);
}
printf("%lld\n",solve(m,r,n));
}
}
