中国剩余定理（CRT）
中国剩余定理出自中国的某本古书，似乎是孙子兵法？（雾
其中有这样一个问题：
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
即，对于这样一个方程组：
我们已知所有(a_i,m_i)，求可行解(x)，可以证明的是，若所有(m_i)互质，那么该方程组有唯一解。
可以构造出一个解：如果有(k)个方程，设(M=prod_{i=1}^k m_i,n_i=frac{M}{m_i})，则有(x=sum_{i=1}^k a_in_in_i^{-1}pmod{M})。
扩展中国剩余定理（EXCRT）
扩展中国剩余定理不要求(m_i)互质，其结论是由数学归纳法得出的，跟CRT实际上没太大关系。这种情况下，方程组的解是不唯一的。
首先考虑两个方程的情况。
假设我们有(xequiv a_1pmod{m_1},xequiv a_2pmod{m_2})，那么显然(x+m_1*t_1=a_1,x+m_2*t_2=a_2)，其中(t_i)为未知数。得出(a_1-a_2=m_1*t_1-m_2*t_2)，根据(Bezout)定理，若(gcd(m_1,m_2)mid (a_1-a_2))，该方程有解。那么我们就可以求出两个方程的情况下的一个解了。
然后考虑多个方程。
假设前(k-1)个方程的解为(x)，记(m=lcm(m_1,m_2,m_3cdots,m_{k-1}))，那么显然前(k-1)个方程的通解是(x+i*m,iin mathbb{Z})。为什么要最小公倍数呢？显然最小公倍数中包含了前(k-1)个数中出现的所有因子，因此(x)加上任意倍的(m)对任意的(m_i)取模答案不变，所以其实把前(k-1)个(m_i)全部乘起来当作(m)也不是不可以。而对于第(k)个方程，我们既要使得解对前(k-1)个方程成立，因此我们取某前(k-1)个方程的某个通解，又要使解对第(k)个方程成立，因此我们要使(x+i*mequiv a_kpmod{m_k})。
现在看到这个方程，(x+i*mequiv a_kpmod{m_k})，可以化为(i*mequiv a_k-xpmod{m_k})我们要求解它，就是求解一个线性同余方程，可以用扩展欧几里得算法得出解。显然，假设前(k)个方程的解为(x')，那么(x'=x+i*m)。
于是我们对方程组进行(k)次扩展欧几里得，就可以得出前(k)个方程的解。
洛谷上板子取模比较神奇，贴一下代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define ll long long
using namespace std;
inline ll read()
{
ll f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
inline ll mul(ll a,ll b,ll p)
{
ll ans=0;
for(;b;b>>=1){
if(b&1) ans=(ans+a)%p;
a=(a+a)%p;
}
return ans;
}
inline ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0){x=1,y=0;return a;}
ll d=exgcd(b,a%b,x,y);
ll z=x;x=y;y=z-y*(a/b);
return d;
}
int n;
int main()
{
n=read();
ll M,gcd,ans=0,x0,y0;
M=read(),ans=read();//第一个方程的最小非负整数解就是它自己
for(register int i=2;i<=n;++i){
ll a,m;
m=read(),a=read();
gcd=exgcd(M,m,x0,y0);
ll k=m/gcd;
x0=mul(x0,((a-ans%m+m)%m)/gcd,m);//至今不知道为什么可以取模
ans+=M*x0;
M*=k;
ans=(ans%M+M)%M;
}
printf("%lld",(ans%M+M)%M);
return 0;
}