結果

問題 No.186 中華風 (Easy)
ユーザー Astral__Astral__
提出日時 2024-09-15 03:35:05
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,886 bytes
コンパイル時間 5,190 ms
コンパイル使用メモリ 309,244 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-15 03:35:12
合計ジャッジ時間 6,292 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 1 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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

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() {
    vec<ll> xs(3), ys(3);
    rep(i, 0, 3) {
        cin >> xs[i] >> ys[i];
    }
    ll c = 0, m = 1;
    rep(i, 0, 3) {
        auto [new_c, new_m] = CRT::crt_2(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