Python程式：計算使數字不互質所需的最少操作次數？

假設我們有兩個數字 A 和 B。現在，在每次操作中，我們可以選擇其中一個數字並將其加 1 或減 1。我們必須找到使 A 和 B 的最大公約數不為 1 所需的最少操作次數。

因此，如果輸入類似於 A = 8，B = 9，則輸出將為 1，因為我們可以選擇 9 並將其增加到 10，所以 8 和 10 不互質。

為了解決這個問題，我們將遵循以下步驟

  • 如果 a 和 b 的最大公約數不等於 1，則

    • 返回 0

  • 如果 a 是偶數或 b 是偶數，則

    • 返回 1

  • 否則，

    • 如果 a + 1 和 b 的最大公約數不等於 1，或者 a - 1 和 b 的最大公約數不等於 1，或者 a 和 b - 1 的最大公約數不等於 1，或者 a 和 b + 1 的最大公約數不等於 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

更新於: 2020年11月10日

258 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告