若m1,m2,m3,m4,m5,…,mr是两两互素的正整数，则同余方程组
x=a1(mod m1)
x=a2(mod m2)
x=a3(mod m3)
…
x=ar(mod mr)
有模 M=m1m2m3…mr的唯一解，即为中国剩余定理。
大概思想就是把解用几个数的和的形式来表示，然后利用拓展欧几里得解方程，依次求出表达式中的每个数。

中国剩余定理解线性同余方程组（解某类线性同余方程组）

poj 1006
hdu 1788

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
    int l,a;
    while(scanf("%d%d",&l,&a),l!=0||a!=0)
    {
        long long ans=1,m;
        for(int i=1;i<=l;i++)
        {
            scanf("%lld",&m);
            ans=ans*m/__gcd(ans,m);
        }
        printf("%lld\n",ans-a);
    }
    return 0;
}

fzu1402
模板：

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
ll a[12],b[12];
int n;
ll _gcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    ll ans=_gcd(b,a%b,x,y);
    ll tmp=x;
    x=y;
    y=tmp-(a/b)*y;
    return ans;
}
ll crt()
{
    ll M=1,ans=0;
    for(int i=1;i<=n;i++)
        M*=a[i];
    for(int i=1;i<=n;i++)
    {
        ll mi=M/a[i];
        ll x,y;
        ll gcd=_gcd(mi,a[i],x,y);
        ans=(ans+mi*b[i]*x)%M;
    }
    if(ans<0)
        ans+=M;
    return ans;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%I64d%I64d",&a[i],&b[i]);
        printf("%I64d\n",crt());//用%lld会WA
    }
    return 0;
}