#1156728 (C++23) No.187 中華風 (Hard)

• 問題: No.187 中華風 (Hard)
• ユーザー: drken1215
• 提出日時: 2026-04-07 00:38:47
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 83 ms / 3,000 ms
• コード長: 4,124 bytes
• コンパイル時間: 3,855 ms
• コンパイル使用メモリ: 340,980 KB
• 実行使用メモリ: 7,972 KB
• 最終ジャッジ日時: 2026-04-07 00:38:56
• 合計ジャッジ時間: 8,349 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
other	AC * 25

ソースコード

//
// 中国剰余定理
//
// cf.
//   中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ
//     https://qiita.com/drken/items/ae02240cd1f8edfc86fd
//
// verified
//   yukicoder 0187 中華風 (Hard)
//     https://yukicoder.me/problems/no/187
//


/*
    x ≡ b[i] (mod. m[i]) を満たす最小の正の整数を x として、x % MOD の値を求める
*/


#include <bits/stdc++.h>
using namespace std;


// Garner's algorithm
// for each step, we solve "coeffs[k] * t[k] + constants[k] = b[k] (mod. m[k])"
//      coeffs[k] = m[0]m[1]...m[k-1]
//      constants[k] = t[0] + t[1]m[0] + ... + t[k-1]m[0]m[1]...m[k-2]

// safe mod
template<class T_VAL, class T_MOD>
constexpr T_VAL safe_mod(T_VAL a, T_MOD m) {
    assert(m > 0);
    a %= m;
    if (a < 0) a += m;
    return a;
}

// mod inv
template<class T_VAL, class T_MOD>
constexpr T_VAL mod_inv(T_VAL a, T_MOD m) {
    assert(m > 0);
    T_VAL b = m, u = 1, v = 0;
    while (b > 0) {
        T_VAL t = a / b;
        a -= t * b, swap(a, b);
        u -= t * v, swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

// if m is not coprime, call this function first
template<class T_VAL>
bool preGarner(vector<T_VAL> &b, vector<T_VAL> &m) {
    assert(b.size() == m.size());
    T_VAL res = 1;
    for (int i = 0; i < (int)b.size(); i++) {
        for (int j = 0; j < i; ++j) {
            T_VAL g = gcd(m[i], m[j]);
            if ((b[i] - b[j]) % g != 0) return false;
            m[i] /= g, m[j] /= g;
            T_VAL gi = gcd(m[i], g), gj = g/gi;
            do {
                g = gcd(gi, gj);
                gi *= g, gj /= g;
            } while (g != 1);
            m[i] *= gi, m[j] *= gj;
            b[i] %= m[i], b[j] %= m[j];
        }
    }
    vector<T_VAL> b2, m2;
    for (int i = 0; i < (int)b.size(); i++) {
        if (m[i] == 1) continue;
        b2.emplace_back(b[i]), m2.emplace_back(m[i]);
    }
    b = b2, m = m2;
    return true;
}

// find x, LCM (m must be coprime)
template<class T_VAL>
pair<T_VAL, T_VAL> Garner(const vector<T_VAL> &b, const vector<T_VAL> &m) {
    assert(b.size() == m.size());
    int num = (int)m.size();
    T_VAL res = 0, lcm = 1;
    vector<long long> coeffs(num, 1), constants(num, 0);
    for (int k = 0; k < num; k++) {
        T_VAL t = safe_mod(b[k] - constants[k], m[k]) * mod_inv(coeffs[k], m[k]) % m[k];
        for (int i = k + 1; i < num; i++) {
            constants[i] = safe_mod(constants[i] + t * coeffs[i], m[i]);
            coeffs[i] = safe_mod(coeffs[i] * m[k], m[i]);
        }
        res += t * lcm;
        lcm *= m[k];
    }
    return make_pair(res, lcm);
}

// find x (%MOD), LCM (%MOD) (m must be coprime)
template<class T_VAL, class T_MOD>
pair<T_VAL, T_VAL> Garner(const vector<T_VAL> &b, const vector<T_VAL> &m, T_MOD MOD) {
    assert(b.size() == m.size());
    assert(MOD > 0);
    int num = (int)m.size();
    T_VAL res = 0, lcm = 1;
    vector<long long> coeffs(num, 1), constants(num, 0);
    for (int k = 0; k < num; k++) {
        T_VAL t = safe_mod(b[k] - constants[k], m[k]) * mod_inv(coeffs[k], m[k]) % m[k];
        for (int i = k + 1; i < num; i++) {
            constants[i] = safe_mod(constants[i] + t * coeffs[i], m[i]);
            coeffs[i] = safe_mod(coeffs[i] * m[k], m[i]);
        }
        res = safe_mod(res + t * lcm, MOD);
        lcm = safe_mod(lcm * m[k], MOD);
    }
    return make_pair(res, lcm);
}


//------------------------------//
// Examples
//------------------------------//

// yukicoder 0187 中華風 (Hard)
void yukicoder_0187() {
    const int MOD = 1000000007;
    int N; 
    cin >> N;
    vector<long long> b(N), m(N);
    bool exist_non_zero = false;
    for (int i = 0; i < N; ++i) {
        cin >> b[i] >> m[i];
        if (b[i]) exist_non_zero = true;
    }
    if (!preGarner(b, m)) {
        cout << -1 << endl;
    } else if (!exist_non_zero) {
        long long lcm = 1;
        for (auto mi : m) lcm = lcm * mi % MOD;
        cout << lcm << endl;
    } else {
        auto [res, lcm] = Garner(b, m, MOD);
        cout << res << endl;
    }
}


int main() {
    yukicoder_0187();
}