【中国剩余定理详解】题解 P1495 【曹冲养猪】

· · 题解

中国剩余定理详解

中国剩余定理是一种用于求解诸如

\begin{cases}x≡a_1\;\;(mod\;\;m_1)\\x≡a_2\;\;(mod\;\;m_2)\\ \cdots \cdots\\x≡a_k\;\;(mod\;\;m_k)\\\end{cases}

形式的同余方程组的定理，其中，m_1,m_2,...,m_k为两两互质的整数，我们的目的，是找出x的最小非负整数解。

一、解法：

至于古人是怎么发现这个算法的，感兴趣的可以自行了解，在此不再赘述（）

我们设 M=\prod_{i=1}^{k}m_i\qquad M_i=\frac{M}{m_i}\qquad M_it_i≡1\;\;(mod\;\;m_i)

其中1≤i≤k。

显然，M表示所有方程组的模的乘积；M_i表示除第i个方程外，其余所有方程的模的乘积；t_i则为M_i的逆元（不懂“逆元”可见下文）。

我们可以构造出一个解x=\sum_{i=1}^{k}a_iM_it_i

由此，任意解x_0即为x+k*M

最小正整数解 x_{min}=x_0\,\%\,M

Notice: 有人可能会问，x=\sum_{i=1}^{k}a_iM_it_i中，M_it_i难道不为1吗？

仔细看，这里x后面跟的是等号，而前面的M_it_i≡1\;\;(mod\;\;m_i)只有在m_i的剩余系中才成立，换句话讲，在实数系中，M_it_i=1是不成立的

二、证明：

其实证明这种东西，搞不搞懂都无所谓

易证，在第i个同余方程中，对于\;∀\;j∈[1,k]，当i≠j时，有

a_jM_jt_j≡0\;(mod\;m_i)

因为M_k里面是有m_i的，而当i=j时，有

a_iM_it_i≡a_i\;(mod\;m_i)

因此，\sum_{i=1}^{k}a_iM_it_i≡a_i\;(mod\;m_i)，满足题意

三、逆元：

若a*a^{-1}≡1\;(mod\;p)，我们就称a^{-1}为a在模p意义下的逆元。

求解逆元的方法主要有如下三种，本篇只介绍使用扩展欧几里得的方法，其余方法各位可自行了解。

1、费马小定理，限制p必须为质数。

2、欧拉定理。

3、扩展欧几里得

扩展欧几里得用于在已知a,b的情况下，求解出一组解x,y，使之满足ax+by=gcd(a,b)=d。此处，我们使用扩展欧几里得求逆元。

标准思路：

ax+by=gcd(a,b) gcd(a,b)=gcd(b,a\%b)

下式（不知道的，可以设a=k_1d，b=k_2d自行尝试证明）代入上式，并设

bx'+a\%b*y'=gcd(b,a\%b)

又因为

a\%b=a-\lfloor\frac{a}{b}\rfloor*b

所以

a*y'+b*(x'-\lfloor\frac{a}{b}\rfloor*y')=gcd(a,b)

故原方程中

x=y',y=x'-\lfloor\frac{a}{b}\rfloor*y'

此外，在开篇的方程组中，我们要求的是M_i在模m_i意义下的逆元，而之前我们设M_i=\frac{M}{m_i}，因此M_i与m_i互质，gcd(M_i,m_i)=1。在这里我们把M_i当做a，把m_i当做b，即ax+by=1，移项得ax=1-by，显而易见ax≡1\;(mod\;b)，因此x即我们要求的逆元。

四、题解：

“如果建了 3个猪圈，剩下 1头猪就没有地方安家了。”

同余方程十分明显： 猪的总数≡无家可归的猪(mod\;\;猪圈数)

#include<cstdio>
#define ll long long
ll n,a[16],m[16],Mi[16],mul=1,X;
inline int rd(){
    int io=0;char in=getchar();
    while(in<'0'||in>'9')in=getchar();
    while(in>='0'&&in<='9')io=(io<<3)+(io<<1)+(in^'0'),in=getchar();
    return io;
}
void exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){x=1;y=0;return ;}
    exgcd(b,a%b,x,y);
    int z=x;x=y,y=z-y*(a/b);
}
int main(){
    n=rd();
    for(int t=1;t<=n;++t){
        int M=rd();m[t]=M;
        mul*=M;
        a[t]=rd();
    }
    for(int t=1;t<=n;++t){
        Mi[t]=mul/m[t];
        ll x=0,y=0;
        exgcd(Mi[t],m[t],x,y);
        X+=a[t]*Mi[t]*(x<0?x+m[t]:x);
    }
    printf("%lld",X%mul);
    return 0;
}