結果

問題 No.187 中華風 (Hard)
ユーザー maine_honzuki
提出日時 2020-12-14 10:58:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,491 bytes
コンパイル時間 2,850 ms
コンパイル使用メモリ 208,432 KB
最終ジャッジ日時 2025-01-17 00:28:53
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 20
権限があれば一括ダウンロードができます

ソースコード

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(vector<T> r, vector<T> m) {
    assert(r.size() == m.size());
    int N = (int)r.size();
    T prod = 1, res = r[0] % m[0];
    for (int i = 1; i < N; i++) {
        prod *= m[i - 1];
        T tmp = ((r[i] - res) * modinv(prod, m[i])) % m[i];
        if (tmp < 0)
            tmp += m[i];
        res += tmp * prod;
    }
    return res;
}

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

    cout << garner(r, m) << endl;
}
0