結果
問題 |
No.186 中華風 (Easy)
|
ユーザー |
|
提出日時 | 2016-12-27 17:53:25 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 691 bytes |
コンパイル時間 | 106 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 10,752 KB |
最終ジャッジ日時 | 2024-07-19 18:28:17 |
合計ジャッジ時間 | 1,451 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#!/usr/bin/env python3 import math lcm = lambda a, b: a * b // math.gcd(a, b) def extgcd(a, b): if b == 0: return 1, 0 else: na, nb = extgcd(b, a % b) return nb, na - a//b * nb def modinv(a, n): return extgcd(a, n)[0] % n def crt(eqn1, eqn2): x1, m1 = eqn1 x2, m2 = eqn2 d = math.gcd(m1, m2) x = x1 + (m1 // d) * (x2 - x1) * modinv(m1 // d, m2 // d) m = lcm(m1, m2) return x % m, m eqn = [ tuple(map(int, input().split())) for _ in range(3) ] ans, _ = crt(eqn[0], crt(eqn[1], eqn[2])) if ans == 0: ans += lcm(eqn[0][1], lcm(eqn[1][1], eqn[2][1])) for x, y in eqn: if ans % y != x: ans = -1 break print(ans)