【中国剩余定理详解】题解 P1495 【曹冲养猪】
Yosame
2019-07-23 21:26:05
# 中国剩余定理详解
中国剩余定理是一种用于求解诸如
$$\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\;\;$猪圈数$)$
```cpp
#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;
}
```