結果
問題 |
No.187 中華風 (Hard)
|
ユーザー |
|
提出日時 | 2016-12-29 23:38:25 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 830 ms / 3,000 ms |
コード長 | 752 bytes |
コンパイル時間 | 263 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 11,264 KB |
最終ジャッジ日時 | 2024-12-15 16:29:30 |
合計ジャッジ時間 | 11,569 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
#!/usr/bin/env python3 import functools 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 n = int(input()) eqn = [ tuple(map(int, input().split())) for _ in range(n) ] ans, _ = functools.reduce(crt, eqn) if ans == 0: ans += functools.reduce(lcm, map(lambda it: it[1], eqn)) for x, y in eqn: if ans % y != x: ans = -1 break else: ans %= 10**9+7 print(ans)