結果

問題 No.2117 中国剰余定理入門
ユーザー AkariAkari
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
def inv_gcd(a, b):
a %= b
if a == 0: return b, 0
s, t = b, a
m0, m1 = 0, 1
while t:
u = s // t
s -= t * u
m0 -= m1 * u
s, t = t, s
m0, m1 = m1, m0
if m0 < 0: m0 += b // s
return s, m0
def crt(r, m):
n = len(r)
r0, m0 = 0, 1
for i in range(n):
r1, m1 = r[i] % m[i], m[i]
if m0 < m1:
r0, r1 = r1, r0
m0, m1 = m1, m0
if m0 % m1 == 0:
if r0 % m1 != r1: return 0, 0
continue
g, im = inv_gcd(m0, m1)
if (r1 - r0) % g: return 0, 0
u1 = m1 // g
x = (r1 - r0) // g % u1 * im % u1
r0 += x * m0
m0 *= u1
if r0 < 0: r0 += m0
return r0, m0
def 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()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0