結果

問題 No.2117 中国剰余定理入門
ユーザー じきお。じきお。
提出日時 2024-04-07 03:47:17
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,837 bytes
コンパイル時間 2,627 ms
コンパイル使用メモリ 248,156 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-01 04:22:17
合計ジャッジ時間 3,383 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#ifdef LOCAL
#include <debug_print.hpp>
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (static_cast<void>(0))
#endif

// ax + by = gcd(a, b) を満たす x, y を求める
pair<ll, ll> extgcd(ll a, ll b) {
    if(b == 0) return {1, 0};
    auto [y, x] = extgcd(b, a % b);
    y -= a / b * x;
    return {x, y};
}

// x ≡ r[i] (mod m[i]) を解き, x ≡ r0 (mod. m0) となる (r0, m0) を返す
// m0 := lcm(m[0], m[1], ...)
pair<ll, ll> crt(const vector<ll>& r, const vector<ll>& m) {
    assert(r.size() == m.size());
    int n = r.size();
    ll r0 = 0, m0 = 1;
    for(int i = 0; i < n; i++){
        assert(1 <= m[i]);
        ll r1 = (r[i] % m[i] + m[i]) % m[i], m1 = m[i], g = gcd(m0, m1);
        // p * m0 + q * m1 = g となる (p, q) を求める
        // このとき p は p * m0 / g ≡ 1 (mod. m1 / g) を満たす
        auto [p, q] = extgcd(m0, m1);
        // r1 ≡ r0 (mod. g) でない場合は解なし
        if((r1 - r0) % g != 0) return {-1, 0};
        // s = (r1 - r0) / g として両辺に s を掛けて
        // p * m0 * s + q * m1 * s = r1 - r0 とする
        // x = r0 + m0 * p * s (= r1 - m1 * p * s) とすると
        // x ≡ r1 (mod. m1), x ≡ r0 (mod. m0) を満たす
        ll u1 = m1 / g;
        ll x = (r1 - r0) / g % u1 * p % u1;
        r0 += m0 * x;
        m0 *= u1; // lcm(m0, m1) = m0 * m1 / g
    }
    r0 = (r0 % m0 + m0) % m0;
    return {r0, m0};
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int B0, B1, C0, C1;
    cin >> B0 >> C0 >> B1 >> C1;
    auto [r, m] = crt({C0, C1}, {B0, B1});
    if(r == -1){
        cout << "NaN" << endl;
    }else{
        cout << r << endl;
    }
}
0