Pythonでシフト後の2つの数表間の最小差を求める方法

問題の概要

2つの数 p と q が与えられたとき、それぞれの数が持つ無限に続く倍数の表（九九の表）を考えます。これらの表をそれぞれ r と s（ただし r, s >= 0）だけシフトした場合、2つのシフト済み表の項同士における最小の差を求めるのが本記事のテーマです。

例として、p = 7、q = 17、r = 6、s = 3 の場合の出力は 0 になります。

• 7の表：[7, 14, 21, 28, 35, 42, 49, ...]
• 17の表：[17, 34, 51, 68, 85, 102, 119, ...]
• 7の表を6シフトした表：[13, 20, 27, 34, 41, 48, 55, ...]
• 17の表を3シフトした表：[20, 37, 54, 71, 88, 105, 122, ...]

どちらのシフト済み表にも 20 という項が含まれているため、最小差は 20 − 20 = 0 となります。

解法のアプローチ

この問題は、最大公約数（GCD）を利用することで非常に効率的に解けます。手順は次のとおりです。

1. g := gcd(p, q) — p と q の最大公約数を求めます。
2. difference := |r − s| mod g — 2つのシフト量の差の絶対値を g で割った余りを計算します。
3. min(difference, g − difference) — difference と g − difference のうち小さい方を答えとして返します。

Pythonでの実装例

以下は、上記のアルゴリズムを Python で実装したコードです。

import math

def get_minimum_diff(p, q, r, s):
    g = math.gcd(p, q)
    difference = abs(r - s) % g
    return min(difference, g - difference)

p = 7
q = 17
r = 6
s = 3
print(get_minimum_diff(p, q, r, s))

入力

7, 17, 6, 3

出力

0

なぜこのアルゴリズムで正しい答えが得られるのか

g を p と q の最大公約数とすると、p の倍数と q の倍数の差は常に g の倍数になります。さらにベズーの等式により、g の任意の倍数は p の倍数と q の倍数の差として表現できます。

したがって、シフト済み表同士の項の差が取り得る値は「(r − s) mod g」の剰余類に属するものだけに限定されます。最小差の候補は difference と g − difference の2つだけであり、このうち小さい方を採用すればよいのです。これにより、全探索を行わずとも O(log(min(p, q))) 程度の計算量で答えを求められます。