結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー tatesoto
提出日時 2025-12-02 01:37:27
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,152 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,031 ms
コンパイル使用メモリ 279,068 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-12-02 01:37:32
合計ジャッジ時間 4,356 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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>;

struct CRT {
    static pll solve(const vll& r, const vll& m) {
        assert(sz(r) == sz(m));
        ll r0 = 0, m0 = 1;
        // Extended GCD via lambda recursion
        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;
            // Use __int128 to prevent overflow during intermediate coefficient calc
            r0 += (ll)((__int128)(r1 - r0) / g % u1 * 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::solve(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