Pythonで理解する蟻本「2-6 双六」(p.108)
この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「2-6 双六」(p.108)
のコードをPythonで書き直したものとなっています。
入力
入力例
4 11
拡張ユークリッドの互除法
def extgcd(a, b):
d = a
if b != 0:
d, y, x = extgcd(b, a % b)
y -= (a // b) * x
else:
x = 1
y = 0
return d, x, y
解答
# 入力
a, b = map(int,input().split())
# 拡張ユークリッドの互除法
def extgcd(a, b):
d = a
if b != 0:
d, y, x = extgcd(b, a % b)
y -= (a // b) * x
else:
x = 1
y = 0
return d, x, y
d, x, y = extgcd(a, b)
if d == 1:
L = [0] * 4
if x > 0:
L[0] += x
else:
L[2] += -x
if y > 0:
L[1] += y
else:
L[3] += -y
print(*L)
else:
print(-1)