結果
問題 | No.2117 中国剰余定理入門 |
ユーザー |
![]() |
提出日時 | 2022-11-04 21:44:24 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 997 bytes |
コンパイル時間 | 83 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 10,880 KB |
最終ジャッジ日時 | 2024-07-18 19:28:02 |
合計ジャッジ時間 | 1,273 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
import sysdef inv_gcd(a, b):a %= bif a == 0: return b, 0s, t = b, am0, m1 = 0, 1while t:u = s // ts -= t * um0 -= m1 * us, t = t, sm0, m1 = m1, m0if m0 < 0: m0 += b // sreturn s, m0def crt(r, m):n = len(r)r0, m0 = 0, 1for i in range(n):r1, m1 = r[i] % m[i], m[i]if m0 < m1:r0, r1 = r1, r0m0, m1 = m1, m0if m0 % m1 == 0:if r0 % m1 != r1: return 0, 0continueg, im = inv_gcd(m0, m1)if (r1 - r0) % g: return 0, 0u1 = m1 // gx = (r1 - r0) // g % u1 * im % u1r0 += x * m0m0 *= u1if r0 < 0: r0 += m0return r0, m0def main():a, b = map(int, input().split())c, d = map(int, input().split())r, m = [b, d], [a, c]z, mod = crt(r, m)if mod == 0:print('NaN')else:print(z)if __name__ == '__main__':main()