結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー drken1215
提出日時 2025-08-11 18:51:27
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 7,609 bytes
コンパイル時間 3,070 ms
コンパイル使用メモリ 282,364 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-08-11 18:51:35
合計ジャッジ時間 8,075 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 RE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

//
// 中国剰余定理
//
// 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;


// 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 pow
template<class T_VAL, class T_MOD>
constexpr T_VAL mod_pow(T_VAL a, T_VAL n, T_MOD m) {
    assert(m > 0);
    T_VAL res = 1;
    while (n > 0) {
        if (n % 2 == 1) res = res * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return res;
}

// 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;
}

// dynamic modint
struct DynamicModint {
    using mint = DynamicModint;
    
    // static menber
    static int MOD;
    
    // inner value
    unsigned int val;
    
    // constructor
    DynamicModint() : val(0) { }
    template<std::signed_integral T> DynamicModint(T v) {
        long long tmp = (long long)(v % (long long)(get_umod()));
        if (tmp < 0) tmp += get_umod();
        val = (unsigned int)(tmp);
    }
    template<std::unsigned_integral T> DynamicModint(T v) {
        val = (unsigned int)(v % get_umod());
    }
    long long get() const { return val; }
    static int get_mod() { return MOD; }
    static unsigned int get_umod() { return MOD; }
    static void set_mod(int mod) { MOD = mod; }
    
    // arithmetic operators
    mint operator + () const { return mint(*this); }
    mint operator - () const { return mint() - mint(*this); }
    mint operator + (const mint &r) const { return mint(*this) += r; }
    mint operator - (const mint &r) const { return mint(*this) -= r; }
    mint operator * (const mint &r) const { return mint(*this) *= r; }
    mint operator / (const mint &r) const { return mint(*this) /= r; }
    mint& operator += (const mint &r) {
        val += r.val;
        if (val >= get_umod()) val -= get_umod();
        return *this;
    }
    mint& operator -= (const mint &r) {
        val -= r.val;
        if (val >= get_umod()) val += get_umod();
        return *this;
    }
    mint& operator *= (const mint &r) {
        unsigned long long tmp = val;
        tmp *= r.val;
        val = (unsigned int)(tmp % get_umod());
        return *this;
    }
    mint& operator /= (const mint &r) {
        return *this = *this * r.inv(); 
    }
    mint pow(long long n) const {
        assert(n >= 0);
        mint res(1), mul(*this);
        while (n) {
            if (n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }
    mint inv() const {
        assert(val);
        return mod_inv((long long)(val), get_umod());
    }

    // other operators
    bool operator == (const mint &r) const {
        return this->val == r.val;
    }
    bool operator != (const mint &r) const {
        return this->val != r.val;
    }
    bool operator < (const mint &r) const {
        return this->val < r.val;
    }
    bool operator > (const mint &r) const {
        return this->val > r.val;
    }
    bool operator <= (const mint &r) const {
        return this->val <= r.val;
    }
    bool operator >= (const mint &r) const {
        return this->val >= r.val;
    }
    mint& operator ++ () {
        ++val;
        if (val == get_umod()) val = 0;
        return *this;
    }
    mint& operator -- () {
        if (val == 0) val = get_umod();
        --val;
        return *this;
    }
    mint operator ++ (int) {
        mint res = *this;
        ++*this;
        return res;
    }
    mint operator -- (int) {
        mint res = *this;
        --*this;
        return res;
    }
    friend istream& operator >> (istream &is, mint &x) {
        long long tmp = 1;
        is >> tmp;
        tmp = tmp % (long long)(get_umod());
        if (tmp < 0) tmp += get_umod();
        x.val = (unsigned int)(tmp);
        return is;
    }
    friend ostream& operator << (ostream &os, const mint &x) {
        return os << x.val;
    }
    friend mint pow(const mint &r, long long n) {
        return r.pow(n);
    }
    friend mint inv(const mint &r) {
        return r.inv();
    }
};
int DynamicModint::MOD;

// Garner's algorithm
// if m is not coprime, call this function first
template<class T_VAL, class T_MOD>
T_VAL preGarner(vector<T_VAL> &b, vector<T_VAL> &m, T_MOD MOD) {
    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 -1;
            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];
        }
    }
    for (int i = 0; i < (int)b.size(); ++i) (res *= m[i]) %= MOD;
    return res;
}

// find x (%MOD), LCM (%MOD) (m must be coprime)
// 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]
template<class T_VAL>
T_VAL Garner(vector<T_VAL> b, vector<T_VAL> m) {
    assert(b.size() == m.size());
    using mint = DynamicModint;
    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++) {
        mint::set_mod(m[k]);
        T_VAL t = ((mint(b[k]) - constants[k]) / coeffs[k]).val;
        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 res;
}

template<class T_VAL, class T_MOD>
T_VAL Garner(vector<T_VAL> b, vector<T_VAL> m, T_MOD MOD) {
    assert(b.size() == m.size());
    assert(MOD > 0);
    using mint = DynamicModint;
    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++) {
        mint::set_mod(m[k]);
        T_VAL t = ((mint(b[k]) - constants[k]) / coeffs[k]).val;
        for (int i = k + 1; i < num + 1; 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 res;
}


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

// yukicoder 0187 中華風 (Hard)
void yukicoder_0187() {
    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;
    }
    const int MOD = 1000000007;
    long long lcm = preGarner(b, m, MOD);
    
    if (!exist_non_zero) cout << lcm << endl;
    else if (lcm == -1) cout << -1 << endl;
    else cout << Garner(b, m, MOD) << endl;
}


int main() {
    yukicoder_0187();
}
0