题解：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}

中国剩余定理（CRT）

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

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

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

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 这一项，若满足通解的形式，直接跳过就行。这种情况下一定是最小解。

#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;
}