クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「2-6 双六」(p.108)

この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「2-6 双六」(p.108)
のコードをPythonで書き直したものとなっています。

入力


a\,b

入力例



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)