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 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告