結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー tatesoto
提出日時 2025-12-02 02:38:05
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,916 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,424 ms
コンパイル使用メモリ 278,656 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-12-02 02:38:11
合計ジャッジ時間 4,105 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;
#define all(a) begin(a), end(a)
#define sz(a) ssize(a)
bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto b) { return a < b ? a = b, 1 : 0; }
#define OVERLOAD_REP(_1, _2, _3, name, ...) name
#define REP1(i, n) for(ll i = 0; (i) < (ll)(n); ++(i))
#define REP2(i, l, r) for(ll i = (ll)(l); (i) < (ll)(r); ++(i))
#define rep(...) OVERLOAD_REP(__VA_ARGS__, REP2, REP1)(__VA_ARGS__)
using pll = pair<ll,ll>;
using vll = vector<ll>;

static pll crt(const vll& r, const vll& m) {
    assert(sz(r) == sz(m));
    ll r0 = 0, m0 = 1;
    auto eg = [&](auto f, ll a, ll b, ll& x, ll& y) -> ll {
        if (!b) return x = 1, y = 0, a;
        ll d = f(f, b, a % b, y, x);
        y -= a / b * x;
        return d;
    };
    rep(i, sz(r)) {
        ll r1 = (r[i] % m[i] + m[i]) % m[i], m1 = m[i];
        if (m0 < m1) swap(r0, r1), swap(m0, m1);
        if (m0 % m1 == 0) {
            if (r0 % m1 != r1) return {0, 0};
            continue;
        }
        ll p, q, g = eg(eg, m0, m1, p, q);
        if ((r1 - r0) % g) return {0, 0};
        ll u1 = m1 / g;
        ll x = (r1 - r0) / g % u1;
        r0 += (ll)((__int128)x * p % u1) * m0;
        m0 *= u1;
        if (r0 < 0) r0 += m0;
    }
    return {r0, m0};
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    // Verify Problem: Yukicoder No.186
    vll x(3), y(3);
    rep(i, 3) cin >> x[i] >> y[i];
    
    // CRT::solve returns {rem, lcm}
    // Logic: ans = rem (mod lcm) -> ans = rem
    pll res = crt(x, y);
    
    if (res.second == 0) {
        cout << -1 << endl;
    } else {
        // Yukicoder 186 requires the smallest POSITIVE integer.
        // If rem == 0, the answer is lcm (since solution must be > 0).
        if (res.first == 0) cout << res.second << endl;
        else cout << res.first << endl;
    }
}
0