結果
問題 |
No.186 中華風 (Easy)
|
ユーザー |
|
提出日時 | 2023-01-17 17:10:42 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 707 bytes |
コンパイル時間 | 1,247 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 54,272 KB |
最終ジャッジ日時 | 2025-01-02 17:38:49 |
合計ジャッジ時間 | 3,269 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 WA * 2 |
ソースコード
from random import randrange as rr from math import gcd def extgcd(a, b, x1=1, y1=0, x2=0, y2=1): if b == 0: return a, x1, y1 q = a//b return extgcd(b, a%b, x2 ,y2, x1-x2*q, y1-y2*q) def crt2(a, b, m1, m2): if a < b: a, b = b, a m1, m2 = m2, m1 d, im1, im2 = extgcd(m1, m2) if a%d != b%d: return None mm = m1//d*m2 x = (a - ((a-b)//d)*(m1*im1)) % mm return x, mm def crt(as_, ms): x = as_[0] mm = ms[0] for a, m in zip(as_[1:], ms[1:]): t = crt2(a, x, m, mm) if t is None: return -1 x, mm = t return x as_, ms = zip(*(map(int, input().split()) for _ in range(3))) print(crt(as_, ms))