Pythonで2点間の直線上に存在する整数座標（格子点）の数を求めるプログラム

2つの点 (p1, q1) と (p2, q2) が与えられたとします。この2点を結ぶ直線上に存在する整数座標（x座標・y座標がともに整数である点、いわゆる格子点）の数を求めるのが課題です。

例として、p1 = 3、q1 = 3、p2 = 6、q2 = 6 が入力された場合、出力は 2 になります。実際に直線を描いてみると、(5, 5) と (6, 6) の2点が直線上に位置していることが確認できます。

解法のアプローチ：最大公約数（GCD）を活用する

この問題は、最大公約数（GCD: Greatest Common Divisor）を使うことで効率的に解けます。2点間の内部に存在する格子点の数は、「x座標の差の絶対値」と「y座標の差の絶対値」の最大公約数から1を引いた値に等しくなります。

具体的な手順は以下の通りです。

• gcd_find() という関数を定義します。引数として x と y を受け取ります。
  • y が 0 と等しい場合は、x を返します。
  • それ以外の場合は、gcd_find(y, x mod y) を再帰的に呼び出して返します（ユークリッドの互除法）。

メインの関数では、次のように処理を行います。

• gcd_find(|p2 − p1|, |q2 − q1|) − 1 を返します。

なぜ最大公約数で求まるのか？

直線上の整数座標の点は、始点から一定の間隔で現れます。dx = |p2 − p1|、dy = |q2 − q1| とおき、その最大公約数を g とすると、(dx/g, dy/g) が隣接する格子点同士をつなぐ基本ベクトルになります。つまり、直線は g ステップで終点に到達するため、両端の2点を除いた内部の格子点の数は g − 1 個となるのです。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def gcd_find(x,y):
    if y == 0:
        return x
    return gcd_find(y,x % y)

def solve(p1,q1,p2,q2):
    return gcd_find(abs(p2 - p1),abs(q2 - q1)) - 1

print(solve(3,3,6,6))

入力

3,3,6,6

出力

2

このように、ユークリッドの互除法によるGCD計算を利用すれば、直線上のすべての点を順番に調べることなく、O(log(min(dx, dy))) の計算量で格子点の数を高速に求めることができます。