题解：P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪

题意简述

我们可以把题意简化成这样：

给定

n

组非负整数

a_i, b_i

，求方程组的最小整数解。

\begin{cases}x\equiv b_1\pmod{a_1}\\x\equiv b_2\pmod{a_2}\\\dots\\x\equiv b_n\pmod{a_n}\end{cases}

看标题就知道这题是啥了，那我们来看看这个定理吧。

接下来是这道题的数学部分：

先说定理，上述同余方程组的通解为

x \equiv M_1N_1b_1+ \cdots + M_nN_nb_n \pmod m

其中

m = a_1a_2\cdots a_n

且对于所有的

i \in [1,n]

，均有

M_i = \frac{m}{a_i}

且

M_iN_i \equiv 1 \pmod {m_i}

看起来是不是很晕，没错，接下来我来带大家证明一下。

我们先假设方程通解

x \equiv x_1 + x_2 + x_3 + \cdots + x_n \pmod {m}

并且由

\begin{cases}x\equiv b_1\pmod{a_1}\\x\equiv b_2\pmod{a_2}\\\dots\\x\equiv b_n\pmod{a_n}\end{cases}

我们希望

x

的形式为

x\equiv b_1+0+0+\dots+0\pmod{a_1}\\ x\equiv 0+b_2+0+\dots+0\pmod{a_2}\\ x\equiv 0+0+b_3+\dots+0\pmod{a_3}\\ \dots\\ x\equiv 0+0+0+\dots+b_n\pmod{a_n}\\ \end{cases}$$ 这样我们就能保证 $x$ 为原方程的解。 好，我们搞清楚这件事后，来看看这组式子需要满足什么呢？ 对于所有的 $0$，保证其对应的那项 $x_i$ 能被对应的模数整除即可，即对于所有的 $i \in [1,n]$，均有

x_i \equiv b_i \pmod {a_i}

且

x_i \equiv 0 \pmod {M_i}

由于 $(M_i, m_i) = 1$，很容易想到取逆元，我们取 $N_i \equiv M_i^{-1} \pmod {m_i}$ 即可，这时 $x_i \equiv b_iM_iN_i \pmod m$ 就可满足上面的条件。 此时，$x \equiv M_1N_1b_1+ \cdots + M_nN_nb_n \pmod m$，证毕！ ---- 蒙了吗？没逝后面还有。下面是编程部分： 题目中已经给出了互质的条件，直接相乘模数即可。我们可以用一个比较巧妙的方法求解，对于所有未满足上面 $x$ 的通解的形式的，我们给最终答案累加上我们要的 $b_iM_iN_i$ 这一项，若满足通解的形式，直接跳过就行。这种情况下一定是最小解。 ```cpp #include<bits/stdc++.h> using namespace std; int a[11], b[11]; int main() { long long tot, ans; int n; cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i] >> b[i]; } ans = b[1];//答案 tot = a[1];//目前已经满足的条件中模数的乘积 for(int i = 2; i <= n; i++) { while(ans % a[i] != b[i]) { ans += tot;//枚举即可 } tot *= a[i]; } cout << ans; } ```