結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー Astral__
提出日時 2024-09-15 03:41:59
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,309 bytes
コンパイル時間 13,812 ms
コンパイル使用メモリ 590,484 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-15 03:42:15
合計ジャッジ時間 14,823 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
std::ostream &operator<<(std::ostream &os, const atcoder::modint998244353 &v) {
    os << v.val();
    return os;
}
std::istream &operator>>(std::istream &is, atcoder::modint998244353 &v) {
    long long x;
    is >> x;
    v = x;
    return is;
}
std::ostream &operator<<(std::ostream &os, const atcoder::modint1000000007 &v) {
    os << v.val();
    return os;
}
std::istream &operator>>(std::istream &is, atcoder::modint1000000007 &v) {
    long long x;
    is >> x;
    v = x;
    return is;
}
#endif
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>

// 任意長整数型
using Bint = boost::multiprecision::cpp_int;
// 仮数部が10進数で1024桁の浮動小数点数型(TLEしたら小さくする)
using Real = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1024>>;
using Rat = boost::rational<Bint>;

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
TT using vvec = vec<vec<T>>;
TT using vvvec = vec<vvec<T>>;
TT using minheap = priority_queue<T, vector<T>, greater<T>>;
TT using maxheap = priority_queue<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    os << p.first << " " << p.second;
    return os;
}

TT ostream &operator<<(ostream &os, const vec<T> &v) {
    for (size_t i = 0; i < v.size(); i++) {
        os << v[i] << (i + 1 != v.size() ? " " : "");
    }
    return os;
}

template <typename T, ll n>
ostream &operator<<(ostream &os, const array<T, n> &v) {
    for (size_t i = 0; i < n; i++) {
        os << v[i] << (i + 1 != n ? " " : "");
    }
    return os;
}

template <typename T> std::ostream &operator<<(ostream &os, const vvec<T> &v) {
    for (size_t i = 0; i < v.size(); i++) {
        os << v[i] << (i + 1 != v.size() ? "\n" : "");
    }
    return os;
}

TT istream &operator>>(istream &is, vec<T> &v) {
    for (size_t i = 0; i < v.size(); i++) {
        is >> v[i];
    }
    return is;
}

#if __has_include(<debug/debug.hpp>)
#include <debug/debug.hpp>
#else
#define dbg(...) true
#define DBG(...) true
#endif

namespace CRT {
template <typename T> T extgcd(T a, T b, T &x, T &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    T d = extgcd<T>(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

template <typename T> T modinv(T a, T MOD) {
    T x, y;
    extgcd(a, MOD, x, y);
    return (x % MOD + MOD) % MOD;
}

template <typename T> bool is_feasable(T x0, T m0, T x1, T m1) {
    T g = gcd(m0, m1);
    return x0 % g == x1 % g;
}

template <typename T> pair<T, T> crt_2(T x0, T m0, T x1, T m1) {
    if (m0 == 0 || m1 == 0) {
        return make_pair(0, 0);
    }
    if (x0 < 0 || x0 >= m0) {
        x0 %= m0;
        if (x0 < 0) x0 += m0;
    }
    if (x1 < 0 || x1 >= m1) {
        x1 %= m1;
        if (x1 < 0) x1 += m1;
    }
    if (m0 < m1) {
        swap(x0, x1);
        swap(m0, m1);
    }

    T a, b;
    T g = extgcd(m0, m1, a, b);
    if (x0 % g != x1 % g) {
        return make_pair(0, 0);
    }
    T lc = lcm(m0, m1);
    T u0 = m0 / g, u1 = m1 / g;
    T x = (x1 - x0) / g * modinv<T>(u0, u1) % u1;
    if (x < 0) x += u1;
    x = x * m0 + x0;
    return make_pair(x, lc);
}
};  // namespace CRT

int main() {
    int n;
    cin >> n;
    vec<ll> xs(n), ys(n);
    rep(i, 0, n) { cin >> xs[i] >> ys[i]; }
    Bint c = 0, m = 1;
    rep(i, 0, 3) {
        auto [new_c, new_m] = CRT::crt_2<Bint>(c, m, xs[i], ys[i]);
        c = new_c;
        m = new_m;
    }
    if (m == 0) {
        cout << -1 << endl;
        return 0;
    }
    if (c == 0) {
        c += m;
    }
    cout << c << endl;
}
0