結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー HAPPA
提出日時 2020-10-06 13:39:03
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 821 bytes
コンパイル時間 76 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2024-07-20 01:46:01
合計ジャッジ時間 1,534 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def CRT(B, M):
    def extGcd(a, b):
        if a == 0:
            return b, 0, 1
        g, y, x = extGcd(b % a, a)
        return g, x - (b // a) * y, y
    b1 = 0
    m1 = 1
    for i in range(len(B)):
        b2 = B[i]
        m2 = M[i]
        d, p, q = extGcd(m1, m2)
        if (b2 - b1) % d != 0:
            return 0, -1
        m = m1 * (m2 // d)
        tmp = (b2 - b1) // d * p % (m2 // d)
        b1 += m1 * tmp
        m1 *= m2 // d
    return b1 % m1, m1


def resolve():
    X, Y = [], []
    for _ in range(3):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)

    res = CRT(X, Y)
    print(res[0] if res[0] else -1)


if __name__ == '__main__':
    resolve()
0