結果
問題 | No.187 中華風 (Hard) |
ユーザー |
![]() |
提出日時 | 2018-09-30 17:50:22 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 808 ms / 3,000 ms |
コード長 | 532 bytes |
コンパイル時間 | 219 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 11,264 KB |
最終ジャッジ日時 | 2024-10-12 09:15:06 |
合計ジャッジ時間 | 11,052 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
def extgcd(a, b): if b: d, y, x = extgcd(b, a % b) y -= (a // b) * x return d, x, y return a, 1, 0 def remainder(V): x = 0; d = 1 for X, Y in V: g, a, b = extgcd(d, Y) x, d = (Y*b*x + d*a*X) // g, d*(Y // g) x %= d return x, d N = int(input()) V = [list(map(int, input().split())) for i in range(N)] x, d = remainder(V) for X, Y in V: if x % Y != X: print(-1) exit(0) MOD = 10**9 + 7 if x == 0: print(d % MOD) else: print(x % MOD)