Luogu P1495 题解

思路

首先看一下题目，可以理解为求解下面的方程：

\[ \left\{ \begin{array}{c} x \equiv b_1 \pmod {a_1} \\ x \equiv b_2 \pmod {a_2} \\ \cdots \\ x \equiv b_n \pmod {a_n} \\ \end{array} \right. \]

很显然可以用中国剩余定理求解，下面讲一下具体过程。

• 求出 \(as = \prod a_i\)。
• 对于每一个方程，求出 \(mi = \frac {as} {a_i}\)，用 exgcd 求出 \(mi\) 在 \(\mod a_i\) 意义下的逆元。
• 更新答案为 \(ans + b_i \times mi \times inv\)，注意对 \(as\) 取模。

简单实现即可，注意对于 Luogu 版本的数据，需要使用 __int128 通过，应该是卡掉 exgcd 了。

代码

#include <iostream>

#define int long long

using namespace std;

__int128 n, a[20], b[20], ans;

__int128 exgcd(__int128 a, __int128 b, __int128 &x, __int128 &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    __int128 d = exgcd(b, a % b, x, y);
    __int128 t = x;
    x = y;
    y = t - a / b * y;
    return d;
}

signed main() {
    int tmp;
    cin >> tmp;
    n = tmp;
    __int128 as = 1;
    for (int i = 1; i <= n; i++) {
        cin >> tmp;
        a[i] = tmp;
        cin >> tmp;
        b[i] = tmp;
        as = as * a[i];
    }
    for (int i = 1; i <= n; i++) {
        __int128 mi = as / a[i], b, y;
        exgcd(mi, a[i], b, y);
        ans = (ans + ::b[i] * mi * b) % as;
    }
    cout << (int) ((ans % as + as) % as);
}