結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー KowerKoint2010
提出日時 2024-06-17 16:11:26
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 144 ms / 3,000 ms
コード長 2,536 bytes
コンパイル時間 3,784 ms
コンパイル使用メモリ 252,396 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-17 16:11:33
合計ジャッジ時間 7,245 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

/// g:gcd(a, b), ax+by=g
struct EG { ll g, x, y; };
EG ext_gcd(ll a, ll b) {
    if (b == 0) {
        if (a >= 0) return EG{a, 1, 0};
        else return EG{-a, -1, 0};
    } else {
        auto e = ext_gcd(b, a % b);
        return EG{e.g, e.y, e.x - a / b * e.y};
    }
}
ll inv_mod (ll x, ll md) {
    auto z = ext_gcd(x, md).x;
    return (z % md + md) % md;
}
template <class T, class U>
T pow_mod(T x, U n, T md) {
    T r = 1 % md;
    x %= md;
    while (n) {
        if (n & 1) r = (r * x) % md;
        x = (x * x) % md;
        n >>= 1;
    }
    return r;
}

// (rem, mod)
pair<ll, ll> crt(const vector<ll>& b, const vector<ll>& c) {
    int n = int(b.size());
    ll r = 0, m = 1;
    for (int i = 0; i < n; i++) {
        auto eg = ext_gcd(m, c[i]);
        ll g = eg.g, im = eg.x;
        if ((b[i] - r) % g) return {0, -1};
        ll tmp = (b[i] - r) / g * im % (c[i] / g);
        r += m * tmp;
        m *= c[i] / g;
    }
    return {(r % m + m) % m, m};
}

ll garner(const vector<ll>& b, vector<ll> m, ll mod) {
    m.push_back(mod);
    int n = m.size();
    vector<ll> coeffs(n, 1);
    vector<ll> consts(n, 0);
    for(int k = 0; k < n - 1; ++k) {
        ll t = (b[k] - consts[k]) * inv_mod(coeffs[k], m[k]) % m[k];
        if(t < 0) t += m[k];
        for(int i = k + 1; i < n; ++i) {
            consts[i] = (consts[i] + t * coeffs[i]) % m[i];
            coeffs[i] = coeffs[i] * m[k] % m[i];
        }
    }
    return consts.back();
}

void coprimize_simulaneous_congruence_equation(ll& r1, ll& m1, ll& r2, ll& m2) {
    ll g = gcd(m1, m2);
    if((r2 - r1) % g != 0) {
        r1 = r2 = m1 = m2 = -1;
        return;
    }
    m1 /= g, m2 /= g;
    ll gi = gcd(g, m1);
    ll gj = g / gi;
    do {
        g = gcd(gi, gj);
        gi *= g, gj /= g;
    } while(g != 1);
    m1 *= gi, m2 *= gj;
    r1 %= m1, r2 %= m2;
}

int main() {
    int n; cin >> n;
    vector<ll> b(n), m(n);
    bool zero = true;
    for(int i = 0; i < n; i++) {
        cin >> b[i] >> m[i];
        for(int j = 0; j < i; j++) {
            coprimize_simulaneous_congruence_equation(b[j], m[j], b[i], m[i]);
            if(b[j] == -1) {
                cout << "-1\n";
                return 0;
            }
        }
        zero &= b[i] == 0;
    }
    ll ans = garner(b, m, 1000000007);
    if(!zero) cout << ans << endl;
    else {
        ll l = 1;
        for(ll mm : m) {
            l = l * mm % 1000000007;
        }
        cout << l << endl;
    }
}
0