結果

問題 No.186 中華風 (Easy)
ユーザー KowerKoint2010KowerKoint2010
提出日時 2024-06-17 16:55:49
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,165 bytes
コンパイル時間 3,248 ms
コンパイル使用メモリ 250,576 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-17 16:55:55
合計ジャッジ時間 5,138 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 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 1 ms
5,376 KB
testcase_11 AC 1 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 AC 1 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 1 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 1 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>
using namespace std;
using ll = long long;

/// g:gcd(a, b), ax+by=g
struct EG { ll g, x, y; };
EG ext_gcd(ll a, ll b) {
    if (b == 0) {
        if (a >= 0) return EG{a, 1, 0};
        else return EG{-a, -1, 0};
    } else {
        auto e = ext_gcd(b, a % b);
        return EG{e.g, e.y, e.x - a / b * e.y};
    }
}
ll inv_mod (ll x, ll md) {
    auto z = ext_gcd(x, md).x;
    return (z % md + md) % md;
}
template <class T, class U>
T pow_mod(T x, U n, T md) {
    T r = 1 % md;
    x %= md;
    while (n) {
        if (n & 1) r = (r * x) % md;
        x = (x * x) % md;
        n >>= 1;
    }
    return r;
}

// (rem, mod)
pair<ll, ll> crt(const vector<ll>& b, const vector<ll>& c) {
    int n = int(b.size());
    ll r = 0, m = 1;
    for (int i = 0; i < n; i++) {
        auto eg = ext_gcd(m, c[i]);
        ll g = eg.g, im = eg.x;
        if ((b[i] - r) % g) return {0, -1};
        ll tmp = (b[i] - r) / g * im % (c[i] / g);
        r += m * tmp;
        m *= c[i] / g;
    }
    return {(r % m + m) % m, m};
}

ll garner(const vector<ll>& b, vector<ll> m, ll mod) {
    m.push_back(mod);
    int n = m.size();
    vector<ll> coeffs(n, 1);
    vector<ll> consts(n, 0);
    for(int k = 0; k < n - 1; ++k) {
        ll t = (b[k] - consts[k]) * inv_mod(coeffs[k], m[k]) % m[k];
        if(t < 0) t += m[k];
        for(int i = k + 1; i < n; ++i) {
            consts[i] = (consts[i] + t * coeffs[i]) % m[i];
            coeffs[i] = coeffs[i] * m[k] % m[i];
        }
    }
    return consts.back();
}

void coprimize_simulaneous_congruence_equation(ll& r1, ll& m1, ll& r2, ll& m2) {
    ll g = gcd(m1, m2);
    if((r2 - r1) % g != 0) {
        r1 = r2 = m1 = m2 = -1;
        return;
    }
    m1 /= g, m2 /= g;
    ll gi = gcd(g, m1);
    ll gj = g / gi;
    do {
        g = gcd(gi, gj);
        gi *= g, gj /= g;
    } while(g != 1);
    m1 *= gi, m2 *= gj;
    r1 %= m1, r2 %= m2;
}

int main() {
    vector<ll> x(3), y(3);
    for(int i = 0; i < 3; i++) {
        cin >> x[i] >> y[i];
    }
    auto [ans, l] = crt(x, y);
    if(l == -1) cout << "-1\n";
    else if(ans == 0) cout << l << endl;
    else cout << ans << endl;
}
0