Pythonで2つの数を互いに素でなくするために必要な最小の操作回数を求めるプログラム

2つの整数 A と B が与えられたとします。1回の操作ごとに、どちらか一方の数を選んで 1 増やすか 1 減らすことができます。このとき、A と B の最大公約数（GCD）が 1 以外になる、つまり2つの数が互いに素でなくなるまでに必要な最小の操作回数を求めるのがこの問題です。

たとえば、入力が A = 8、B = 9 の場合、出力は 1 となります。B の 9 を選んで 10 に増やせば、gcd(8, 10) = 2 となり、2つの数は互いに素ではなくなるからです。

解き方の考え方

この問題には重要な性質があります。それは、答えが高々 2 回で足りるということです。2回の操作で両方の数を偶数に変更できれば、GCD は必ず 2 以上になるためです。この性質を利用すると、次のように場合分けすることで効率的に答えを求められます。

1. GCD(A, B) ≠ 1 の場合
   すでに互いに素ではないため、操作は一切不要です。0 を返します。

2. A または B のどちらかが偶数の場合
   互いに素であるという前提があるため、このケースは「片方が偶数・もう片方が奇数」の組み合わせです。奇数の方を ±1 すれば偶数になり、両方とも偶数となるので GCD は必ず 2 以上になります。したがって 1 を返します。

3. 両方とも奇数の場合
   1回の操作で片方だけを偶数にしても、もう片方は奇数のままなので、GCD が 1 のまま残る可能性があります。そこで次のように判定します。

   • (a+1, b)、(a−1, b)、(a, b−1)、(a, b+1) のいずれかの組み合わせで GCD が 1 以外になれば、1 を返します。
   • どの組み合わせでも成立しなければ、2 を返します。2回の操作で両方を偶数にすれば必ず条件を満たせるからです。

理解を深めるために、以下の実装を見てみましょう。

実装例（Python）

from math import gcd

class Solution:
    def solve(self, a, b):
        # すでに互いに素でない場合は 0
        if gcd(a, b) != 1:
            return 0
        # どちらかが偶数なら 1 回の操作で可能
        if a % 2 == 0 or b % 2 == 0:
            return 1
        # 両方とも奇数の場合：1 回の操作で達成できるかを確認
        elif (gcd(a + 1, b) != 1 or gcd(a - 1, b) != 1 or
              gcd(a, b - 1) != 1 or gcd(a, b + 1) != 1):
            return 1
        # どの操作でも不可能な場合は 2 回必要
        else:
            return 2

ob = Solution()
A = 8
B = 9
print(ob.solve(A, B))

入力

A = 8, B = 9

出力

1

計算量について

ユークリッドの互除法による GCD 計算は O(log(min(a, b))) で行えるため、このアルゴリズム全体の計算量も O(log(min(a, b))) となります。GCD の呼び出し回数は定数回（最大5回程度）に抑えられるため、非常に大きな数が入力されても高速に動作します。