結果
| 問題 | No.186 中華風 (Easy) |
| コンテスト | |
| ユーザー |
shinnshinn
|
| 提出日時 | 2024-04-20 10:22:05 |
| 言語 | Python3 (3.15.2 + numpy 2.5.4 + scipy 1.18.1 + ACL) |
| 結果 |
WJ
不安定
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 812 bytes |
| 記録 | |
| 最終ジャッジ日時 | 2026-11-11 03:27:21 |
|
ジャッジサーバーID (参考情報) |
judge4_0 / judge3_0 |
(要ログイン)
ソースコード
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a%b)
def extgcd(a, b):
#拡張ユークリッド互除法
#ax + by = gcd(a, b)となる(x, y)を求めます
if b == 0:
return [1, 0]
q = a//b
r = a%b
s, t = extgcd(b, r)
y = s - q*t
return [t, y]
def CRT(rs, ms):
R = 0
M = 1
for r, m in zip(rs, ms):
g = gcd(M, m)
# assert r%g == R%g
if r%g != R%g:
return [-1, -1]
s, _ = extgcd(M, m)
lcm = m*M // g
R += (r - R)//g * M * s
R %= lcm
M = lcm
return [R, M]
x = []
y = []
for i in range(3):
X, Y = map(int, input().split())
x.append(X)
y.append(Y)
ans = CRT(x, y)
if ans[0] == 0:
print(ans[1])
else:
print(ans[0])
shinnshinn