結果
問題 |
No.186 中華風 (Easy)
|
ユーザー |
|
提出日時 | 2023-01-22 02:55:14 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 632 bytes |
コンパイル時間 | 158 ms |
コンパイル使用メモリ | 82,172 KB |
実行使用メモリ | 66,156 KB |
最終ジャッジ日時 | 2024-06-24 07:54:32 |
合計ジャッジ時間 | 1,845 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 RE * 2 |
ソースコード
ls = [tuple(map(int,input().split())) for _ in range(3)] 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 # V = [(X_i, Y_i), ...]: X_i (mod Y_i) def remainder(V): x = 0; d = 1 for X, Y in V: g, a, b = extgcd(d, Y) if (X-x)%g: return -1,-1 # 理屈は分からんが駄目な時にこれを出力 x, d = (Y*b*x + d*a*X) // g, d*(Y // g) x %= d if x == 0: return d return x, d # 数字≡x(mod d)ならいいという情報? 最小の数字はx print(remainder(ls)[0])