結果
問題 | No.186 中華風 (Easy) |
ユーザー |
![]() |
提出日時 | 2021-12-04 18:14:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 42 ms / 2,000 ms |
コード長 | 791 bytes |
コンパイル時間 | 216 ms |
コンパイル使用メモリ | 82,108 KB |
実行使用メモリ | 52,864 KB |
最終ジャッジ日時 | 2024-07-07 00:38:32 |
合計ジャッジ時間 | 2,018 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
def ChineseRem(b1, b2, m1, m2): from math import gcd def extGCD(a, b): # ax + by = gcd(a, b)の解を求める if b == 0: return 1, 0 q = a // b r = a % b X, Y = extGCD(b, r) return Y, X - q * Y if (b1 - b2) % gcd(m1, m2) != 0: return None, None d = gcd(m1, m2) lcm = m1 * m2 // d p, q = extGCD(m1, m2) return ((b2 - b1) // d * m1 * p + b1) % lcm, lcm X, M = [0] * 3, [0] * 3 for i in range(3): X[i], M[i] = map(int, input().split()) x, mod = ChineseRem(X[0], X[1], M[0], M[1]) if x is None: print(-1) else: ans, lcm = ChineseRem(x, X[2], mod, M[2]) if ans is None: print(-1) else: if ans == 0: print(lcm) else: print(ans)