結果

問題 No.186 中華風 (Easy)
ユーザー とばりとばり
提出日時 2018-09-21 06:36:57
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,273 bytes
コンパイル時間 1,643 ms
コンパイル使用メモリ 175,968 KB
実行使用メモリ 4,504 KB
最終ジャッジ日時 2023-09-25 10:39:01
合計ジャッジ時間 2,612 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>

using int64 = long long;
using uint64 = unsigned long long;
using int128 = __int128_t;

inline int128 mod(int128 a, int128 m) { return (a % m + m) % m; }

std::tuple<int128, int128, int128> extGCD(int128 a, int128 b) {
    if (b == 0) return std::make_tuple((int128)1, (int128)0, a);

    int128 s, t, g;
    std::tie(s, t, g) = extGCD(b, a % b);
    return std::make_tuple(t, s - (a / b) * t, g);
}

std::tuple<int128, bool> CRT(std::vector<int128> b, std::vector<int128> m) {
    int n = b.size();

    int128 B = 0, M = 1;
    for (int i = 0; i < n; i++) {
        int128 p, q, d;
        std::tie(p, q, d) = extGCD(M, m[i]);

        if ((b[i] - B) % d != 0) return std::make_tuple(0, false);

        // r = B
        int128 s = (b[i] - B) / d;
        B = B + s * M * p;
        M = (M / d) * m[i];

        B = mod(B, M);
    }
    return std::make_tuple(B, true);
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    std::vector<int128> X(3), Y(3);
    for (int i = 0; i < 3; i++) {
        int64 x, y;
        std::cin >> x >> y;

        X[i] = x; Y[i] = y;
    }

    int128 x;
    bool ok;
    std::tie(x, ok) = CRT(X, Y);

    if (!ok) x = -1;
    std::cout << (int64)x << std::endl;

    return 0;
}
0