中国剩余定理

导入

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

上述的一段诗句出自 《孙子算经》 （该书中首次提到了同余方程组问题，以及此问题的解法，因此有些地方也会将中国剩余定理称为孙子定理）。 言归正转 ，上述诗句翻译成现代数学的语言即为：

有一个正整数n,满足n%3==2，n%5==3，n%7==2，求这个正整数n。

毫无疑问，满足条件的最小正整数n有无穷多个，我们需要解决的问题是n的最小值为多少。那么如何解决这个问题呢？我们先来了解了解古人的解法：

三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知。

仅仅二十八个字，古人便将上述问题的解题过程讲述得即为具体，可能，你却听得一头雾水。别急，我先翻译一下：

23≡2*70+3*21+2*15(mod 105)

//≡为恒等号
//注意70,21,15这三个数，以下有用

答曰：二十三。

当然，我们可以轻松地验证出23的确为符合要求的最小正整数解， 但是 ，我们所要了解的是如何快速地求出最小正整数解n，这就需要我们熟练地掌握 中国剩余定理 。

---

同余

中国剩余定理是用以解决同余方程组问题，那么我们要想学懂中国剩余定理，那么同余方程的概念及同余方程的一些性质便好比先行管。

同余：如果有两个数a与b，且有一除数c，使得a mod c≡b mod c，那么我们就说a和b关于c同余。记作a≡b(mod c)。

对于两个数a与b与除数c，有一下一些性质：

性质一：若a1≡b1(mod c),a2≡b2(mod c)，则a1+a2≡b1+b2(mod c)
性质二：若a1≡b1(mod c)，则a1*d≡b1*d(mod c)

---

古人的思维

既然大家此时此刻都已经了解同余方程，那么我们便将原问题转化为以下的同余方程组：

n≡2(mod 3)
n≡3(mod 5)
n≡2(mod 7)

设x为上述同余方程组的最小正整数解，则x+105*k(k为整数)虽然不是最小正整数解，但也是上述同余方程组的一组可行解(性质一,105*k%c比为0)

接着解下列三个特殊同余方程组的解

同余方程组一：
x≡1(mod 3)
x≡0(mod 5)
x≡0(mod 7)

同余方程组二：
x≡0(mod 3)
x≡1(mod 5)
x≡0(mod 7)

同余方程组三：
x≡0(mod 3)
x≡0(mod 5)
x≡1(mod 7)

以同余方程组一为例，由于x≡0(mod 5)且x≡0(mod 7)，故x为35的倍数，则设x=35y,则x≡1(mod 3)就转化成了35y≡1(mod 3)，即有35y+3yy==1，扩展欧几里德定理可以求得y=2，于是x=35*2=70(mod 105)。同理，同余方程组二的解为x=21；同余方程组三的解为x=15。

同样考虑同余方程组一，由性质二得出x*2=1*2(mod 105)，故满足n≡2(mod 3)的解为x1=35。同理，x2=63；x3=30。

所以：最小正整数解n=(x1+x2+x3)%105=(35+63+30)%105=23。

---

中国剩余定理

接下来我们正式谈谈中国剩余定理。先讲讲中国剩余定理的一般形式：

已知b1,b2,b3,…,bn为互质的正整数，且有：
n≡a1(mod b1)
n≡a2(mod b2)
n≡a3(mod b3)
……
n≡an(mod bn)
求最小正整数解n。

转化

n1≡1(mod b1)
n2≡0(mod b2)
n3≡0(mod b3)
……
nn≡0(mod bn)


n1≡0(mod b1)
n2≡1(mod b2)
n3≡0(mod b3)
……
nn≡0(mod bn)


……


n1≡0(mod b1)
n2≡0(mod b2)
n3≡0(mod b3)
……
nn≡1(mod bn)

重点：考虑第一组方程组，设m=b1*b2*b3*…*bn,m1=m/b1,n1=m1*x,则方程等价于m1*x≡1(mod b1)→m1*x+b1*y≡1,扩欧得出x，则n1=m1*x，所以方程组的解为n=a1*n1+a2*n2+…+an*nn(mod m)

---

模板

模板题：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int n=11;
ll a[n],b[n];

void gcd(ll n1,ll n2,ll &x,ll &y)
{
    if (n1%n2==0) {x=0,y=1;return;}
    gcd(n2,n1%n2,x,y);
    ll t;
    t=x,x=y,y=t-(n1/n2)*y;
}

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

int main()
{
    int n,i;
    while (~scanf("%d",&n))
    {
        for (i=1;i<=n;++i) cin>>a[i]>>b[i];
        cout<<calc(n)<<endl;
    }
    return 0;
}