数论之中国剩余定理

中国剩余定理是中国古代求解一次同余式组（见同余）的方法，是数论中一个重要定理，又称孙子定理。

孙子定理

　　孙子定理主要用来求解模线性不定方程组。

　　对于方程组：

　　　　　　　　 x₀≡a₀(mod b₀)

　　　　　　　x₁≡a₁(mod b₁)

　　　　　　　x₂≡a₂(mod b₂)　

　　　　　　　.  .  .  

　　　　　　　x_n≡a_n(mod b_n)

　　设m=b₀*b₁*b₂*...*b_n，m_i=m/b_i

　　得到方程组

　　　　　　m_ix_i+b_iy_i=1

　　扩欧求解后，原模线性方程组的解为：

　　　　　　∑m_i*a_i*x_i  mod m

看代码吧：

#include <cstdio>
using namespace std;
const int MAXN=10050;
int n;
int a[MAXN],b[MAXN];

void exgcd(long long a,long long b,long long &x,long long &y)
{
    if(a%b==0)
    {
        x=0;y=1;return ;
    }
    exgcd(b,a%b,x,y);
    long long t=x;
    x=y;y=t-a/b*y;
}

long long China_Reminder(int n)
{
    long long m=1,mi,res=0,x,y;
    for(int i=1;i<=n;i++)m*=b[i];
    for(int i=1;i<=n;i++)
    {
        mi=m/b[i];
        exgcd(mi,b[i],x,y);
        x=(x%b[i]+b[i])%b[i];
        res=(res+mi*a[i]*x%m)%m;
    }
    return (res+m)%m;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d %d",&a[i],&b[i]);
    printf("%lld\n",China_Reminder(n));
    return 0;
}

例题：fzu1402 猪的安家