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

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

Pythonで理解する蟻本「2-6 線分上の格子点の個数」(p.107)

Pythonで理解する蟻本（プログラミングコンテストチャレンジブック）

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-6 線分上の格子点の個数」(p.107)
のコードをPythonで書き直したものとなっています。

入力


x_1\,y_1\\x_2\,y_2

入力例



1 11
5 3


最大公約数を求める関数

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

解答

# 入力
x1, y1 = map(int,input().split())
x2, y2 = map(int,input().split())

# 最大公約数を求める関数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

ans = gcd(abs(x1 - x2), abs(y1 - y2)) - 1
print(ans)