原理

• 中国剩余定理：给定一组两两互质的数据$m_1, m_2, …,m_k$，求如下方程组的解x的值：

$$ \begin{cases} x = a_1 \ (mod \ m_1) \\\\ x = a_2 \ (mod \ m_2) \\\\ … \\\\ x = a_k \ (mod \ m_k) \end{cases} $$

令$M = m_1 \times m_2 \times … \times m_k$，$M_i = \frac{M}{m_i}$。因为$m_1, m_2, …,m_k$两两互质，所以$M_i$和$m_i$互质，因此可以求出$M_i$模$m_i$的逆（逆元）即解方程$M_i \times x = 1 \ (mod \ m_i)$，解出x就是$M_i$模$m_i$的逆，记作$M_i^{-1}$。

则$x = a_1 \times M_1 \times M_1^{-1} + a_2 \times M_2 \times M_2^{-1} + … + a_k \times M_k \times M_k^{-1}$。

• 证明很简单，直接将x带入方程组验算一遍即可。这里演示第一项，已知：$M_i \times M_i^{-1} = 1 \ (mod \ m_i)$，所以$a_i \times M_i \times M_i^{-1} = a_i \ (mod \ m_i)$。对于第一项，有$a_1 \times M_1 \times M_1^{-1} = a_1 \ (mod \ m_1)$，对于后面的每一项的$M_i(2 \le i \le k)$都能被$m_1$整除，因此$x = a_1 \ (mod \ m_1)$成立。

• 求$M_i$模$m_i$的逆，这里不能使用快速幂求逆元（因为$m_i$不一定是质数），需要使用扩展欧几里得算法求解，即求解方程$M_i \times x = 1 \ (mod \ m_i)$，可以参考AcWing 878. 线性同余方程的做法。

• 注意：中国剩余定理有个很重要的前提，即数据$m_1, m_2, …,m_k$两两互质，缺少这个前提不能使用!!!

分析

• 本题相当于给定了很多两两互质的$a_i$，有方程组：$x \equiv b_i \ (mod \ a_i)$。让求解最小的x。

• 这一题比AcWing 204. 表达整数的奇怪方式更加简单，就是中国剩余定理的直接应用。按照中国剩余定理的步骤求解一遍即可。

• 这里需要注意一点，我们要输出最小的符合要求的整数，如果x是一个解，则x+M也是一个解。

代码

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 10;

int A[N], B[N];  // x = B[i] (mod A[i])

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() {

    int n;
    cin >> n;

    LL M = 1;
    for (int i = 0; i < n; i++) {
        cin >> A[i] >> B[i];
        M *= A[i];
    }

    LL res = 0;
    for (int i = 0; i < n; i++) {
        LL Mi = M / A[i];
        LL ti, x;  // ti是Mi关于A[i]的逆元
        exgcd(Mi, A[i], ti, x);
        res += B[i] * Mi * ti;
    }

    cout << (res % M + M) % M << endl;

    return 0;
}