結果
問題 | No.2117 中国剰余定理入門 |
ユーザー |
![]() |
提出日時 | 2022-11-13 20:27:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 44 ms / 2,000 ms |
コード長 | 732 bytes |
コンパイル時間 | 181 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 52,480 KB |
最終ジャッジ日時 | 2024-09-15 01:59:25 |
合計ジャッジ時間 | 1,855 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
import mathdef Chinese_Surplus_Theorem(b1,b2,m1,m2):def Euclidean_Algorithm(a,b,d):a,b = max(a,b),min(a,b)if a == d and b == 0:return 1,0div,mod = divmod(a,b)nx,ny = Euclidean_Algorithm(b,mod,d)res = (ny,nx - div*ny)return resd = math.gcd(m1,m2)if m1 < m2:m1,m2 = m2,m1b1,b2 = b2,b1if b1 % d != b2 % d:return 0,0p,q = Euclidean_Algorithm(m1,m2,d)s = (b2-b1)//dreturn (b1 + s*m1*p) % (m1*m2//d) ,m1*m2//db0,c0 = map(int,input().split())b1,c1 = map(int,input().split())c0 %= b0c1 %= b1x,y = Chinese_Surplus_Theorem(c0,c1,b0,b1)if c0 == c1 == 0:print(0)elif x == 0:print("NaN")else:print(x)