結果
問題 |
No.187 中華風 (Hard)
|
ユーザー |
|
提出日時 | 2021-03-07 12:59:20 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 758 bytes |
コンパイル時間 | 150 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 10,880 KB |
最終ジャッジ日時 | 2024-10-08 23:13:00 |
合計ジャッジ時間 | 2,033 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 WA * 15 |
ソースコード
def CRT(BMlist): # Extended Euclidean Algorithm 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 r = 0; M = 1 for b,m in BMlist: d,p,q = extgcd(M,m) if (b-r)%d != 0: return 0,-1 r += M*((b-r)//d*p%(m//d)) M *= m//d r %= sml; M %= sml return r%sml,M%sml import math BMlist = [] ans = 1 sml = 10**9+7 N = int(input()) for i in range(N): x,y = map(int, input().split()) BMlist.append((x,y)) g = math.gcd(ans,y) ans = ((ans*y)//g)%sml r,m = CRT(BMlist) if r != 0: print(r) elif m == -1: print(-1) else: if ans != 1: print(ans) else: print(0)