题目描述

自从朱最学搞定了 QQ 农场以后，就开始捉摸去 QQ 牧场干些事业，不仅在自己的牧场养牛，还到阿九的牧场放牛！

阿九很生气，有一次朱最学想知道阿九牧场奶牛的数量，于是阿九想狠狠耍朱最学一把。
举个例子，假如有 16 头奶牛。
1) 如果建了 3 个牛棚，剩下 1 头牛就没有地方安家了。
2) 如果建造了 5 个牛棚，但是仍然有 1 头牛没有地方去。
3) 然后如果建造了 7 个牛棚，还有2头没有地方去。

你作为阿九的私人秘书理所当然要将准确的奶牛数报给阿九，你该怎么办？

样例1

输入：

3
3 1
5 1
7 2

输出：

16

样例2

输入：

2
99982 19823
99983 92834

输出：

2696734327

$Code$

#include <iostream>
#include <vector>
using namespace std;
vector<long long> a;
vector<long long> b;

// 扩展欧几里得算法
long long exgcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) {
        x = 1,y = 0;
        return a;
    }
    int d=exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

// 中国剩余定理
long long CRT(int n, vector<long long> a, vector<long long> b) {
    long long M = 1;
    // 计算 M 的过程 -> M = a1 * a2 * a3 * …… * an
    for (int i=0;i<a.size();i++) {
        M *= a[i];
    }
    long long x = 0;
    for (int i = 0; i < n; ++i) {
        long long Mi = M / a[i];// 计算n个 Mi -> Mi = M/ai
        long long Mi_ni, _;
        // 求 Mi 在模 mi 下的逆元 Mi_ni，即找到 Mi_ni 使得 Mi*Mi_ni ≡ 1(mod mi)
        long long d=exgcd(Mi, a[i], Mi_ni, _);
        x += b[i] * Mi * Mi_ni;
    }
    return (x % M + M) % M;  // 确保结果为非负
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int a_,b_;
        cin >> a_ >> b_;
        a.push_back(a_);
        b.push_back(b_);
    }
    cout << CRT(n, a, b) << endl;
    return 0;
}