結果

問題 No.187 中華風 (Hard)
ユーザー kyuna
提出日時 2020-02-07 03:52:03
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 202 ms / 3,000 ms
コード長 2,079 bytes
コンパイル時間 876 ms
コンパイル使用メモリ 75,912 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-25 07:11:15
合計ジャッジ時間 4,468 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int MOD = (int)1e9 + 7;
inline long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }

long long extgcd(long long a, long long b, long long &x, long long &y) {
    for (long long u = y = 1, v = x = 0; a; ) {
        long long q = b / a;
        swap(x -= q * u, u);
        swap(y -= q * v, v);
        swap(b -= q * a, a);
    }
    return b;
}

long long modinv(long long a, long long m) {
    long long x, y;
    extgcd(a, m, x, y);
    return (x + m) % m;
}

long long pre_garner(vector<long long> &b, vector<long long> &m, long long mod) {
    long long res = 1;
    for (int i = 0; i < (int)b.size(); i++) for (int j = 0; j < i; j++) {
        long long g = gcd(m[i], m[j]);
        if ((b[i] - b[j]) % g != 0) return -1;
        m[i] /= g, m[j] /= g;
        long long gi = gcd(m[i], g), gj = g / gi;
        while ((g = gcd(gi, gj)) != 1) gi *= g, gj /= g;
        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;
}

long long garner(vector<long long> b, vector<long long> m, long long mod) {
    m.push_back(mod);   // sentinel
    vector<long long> coeffs((int)m.size(), 1);
    vector<long long> constants((int)m.size(), 0);
    for (int k = 0; k < (int)b.size(); k++) {
        long long a = (b[k] - constants[k]) * modinv(coeffs[k], m[k]);
        long long t = (a % m[k] + m[k]) % m[k];
        for (int i = k + 1; i < (int)m.size(); i++) {
            (constants[i] += t * coeffs[i]) %= m[i];
            (coeffs[i] *= m[k]) %= m[i];
        }
    }
    return constants.back();
}

int main() {
    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;
    }
    long long lcm = pre_garner(b, m, MOD);
    if (!exist_non_zero || lcm == -1) return !(cout << lcm << endl);
    cout << garner(b, m, MOD) << endl;
    return 0;
}
0