中国剩余定理

设 $x\in Z$，有

$$ \begin{cases} x \equiv a_1\pmod{m_1} \\\ x \equiv a_2\pmod{m_2} \\\ \vdots \\\ x \equiv a_n\pmod{m_n} \end{cases} $$

令 $\begin{cases}M = m_1m_2m_3\dots m_n \\\M_i=\dfrac{M}{m_i} \\\ {t_i是M_i关于m_i的逆元，即M_it_i\equiv1\pmod{m_i}} \end{cases}$

则
$$ x = \sum_{i=1}^na_iM_it_i $$

本题是一道中国剩余定理的裸题，直接用输入数据套公式即可，具体详解在代码的注释中

Code

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 15;

int n;
int a[N], m[N];

void exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) x = 1, y = 0;
    else {
        exgcd(b, a % b, y, x);
        y -= a / b * x;
    }
}
int main() {
    cin >> n;
    LL M = 1;
    for (int i = 0; i < n; ++ i) {
        cin >> m[i] >> a[i];
        M *= m[i];  //读入mi的同时计算M
    }
    LL res = 0;
    for (int i = 0; i < n; ++ i) {
        LL Mi = M / m[i];   //计算Mi = M/mi
        LL ti, y;
        //这一步是求逆元，根据逆元公式的衍生公式可以得到 ti * Mi + y * mi = 1
        exgcd(Mi, m[i], ti, y);
        res += a[i] * Mi * ti;  //计算的同时累加到res中（上述公式里有个sum需要累加）
    }
    cout << (res % M + M) % M << endl;  //对于任意x+kM都是满足要求的解，但目标是输出最小的正整数x，因此取模即可
    return 0;
}