結果

問題 No.187 中華風 (Hard)
ユーザー maine_honzuki
提出日時 2020-12-14 11:34:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 333 ms / 3,000 ms
コード長 2,870 bytes
コンパイル時間 2,108 ms
コンパイル使用メモリ 210,252 KB
最終ジャッジ日時 2025-01-17 00:29:21
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

//ax + by = gcd(a,b)
template <typename T>
T extgcd(T a, T b, T& x, T& y) {
    if (b) {
        T d = extgcd(b, a % b, y, x);
        y -= a / b * x;
        return d;
    } else {
        x = 1;
        y = 0;
        return a;
    }
}

//modular inverse of a mod m
template <typename T>
T modinv(T a, T m) {
    T x, y;
    T d = extgcd(a, m, x, y);
    if (d != 1)
        return -1;
    x %= m;
    if (x < 0)
        x += m;
    return x;
}

//res = r (mod m)
template <typename T>
T garner_mod(vector<T> r, vector<T> m, ll MOD) {
    assert(r.size() == m.size());
    int N = (int)r.size();
    vector<T> v(N);
    v[0] = r[0] % m[0];
    if (v[0] == 0) v[0] = m[0];
    for (int i = 1; i < N; i++) {
        T prod = 1;
        for (int j = 0; j < i; j++) {
            (prod *= m[j]) %= m[i];
        }
        T tmp = v[i - 1];
        for (int j = i - 2; j >= 0; j--) {
            tmp = (tmp * m[j] % m[i] + v[j]) % m[i];
        }
        v[i] = (r[i] - tmp) * modinv(prod, m[i]) % m[i];
        if (v[i] < 0)
            v[i] += m[i];
    }
    T ret = 0;
    for (int i = N - 1; i >= 0; i--) {
        ret = (ret * m[i] % MOD + v[i]) % MOD;
    }
    return ret;
}

template <typename T>
vector<pair<T, int>> prime_factorize(T n) {
    vector<pair<T, int>> ret;
    for (T i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int num = 0;
            while (n % i == 0) {
                num++;
                n /= i;
            }
            ret.push_back({i, num});
        }
    }
    if (n != 1)
        ret.push_back({n, 1});
    return ret;
}

template <typename T>
T pow(T x, int n) {
    T res = 1;
    while (n) {
        if (n & 1)
            res *= x;
        x *= x;
        n >>= 1;
    }
    return res;
}

int main() {
    int N;
    cin >> N;
    vector<ll> X(N), Y(N);
    for (int i = 0; i < N; i++) {
        cin >> X[i] >> Y[i];
    }

    map<ll, pair<int, ll>> mods;
    for (int i = 0; i < N; i++) {
        auto V = prime_factorize(Y[i]);
        for (auto& [m, power] : V) {
            ll rem = X[i] % pow(m, power);
            if (!mods.count(m)) {
                mods[m] = {power, rem};
            } else {
                auto& [power_bef, rem_bef] = mods[m];
                if ((rem - rem_bef) % pow(m, min(power, power_bef)) != 0) {
                    cout << -1 << endl;
                    exit(0);
                } else {
                    if (power_bef < power) {
                        power_bef = power;
                        rem_bef = rem;
                    }
                }
            }
        }
    }

    vector<ll> m, r;
    for (auto& [mod, p] : mods) {
        m.emplace_back(pow(mod, p.first));
        r.emplace_back(p.second);
    }

    const ll MOD = 1e9 + 7;
    cout << garner_mod(r, m, MOD) << endl;
}
0