Pythonで数を互いに素にしないために必要な操作の最小数を数えるプログラム？

AとBの2つの数値があるとします。これで、各演算で、数値のいずれかを選択して1ずつインクリメントするか、1ずつデクリメントできます。最大公約数になるように必要な最小の演算数を見つける必要があります。 AとBの間は1ではありません。

したがって、入力がA =8、B =9の場合、出力は1になります。これは、9を選択してから10に増やすことができるため、8と10は互いに素ではありません。

これを解決するには、次の手順に従います。

• aとbのgcdが1と同じでない場合、

  • 0を返す

• aが偶数またはbが偶数の場合、

  • 1を返す

• それ以外の場合

  • a+1とbのgcdが1と同じでない場合またはa-1とbのgcdが1と同じでない場合またはaとbのgcd-1が1と同じでない場合またはaとb+1のgcdが1、次に

    • 1を返す

  • それ以外の場合

    • 2を返す

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

例

from math import gcd

class Solution:
   def solve(self, a, b):
      if gcd(a, b) != 1:
         return 0
      if a % 2 == 0 or b % 2 == 0:
         return 1
      else:
         if (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
      else:
         return 2

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

入力

8,9

出力

1