โปรแกรมนับจำนวนการดำเนินการขั้นต่ำที่จำเป็นในการทำให้ตัวเลขไม่ใช่ coprime ใน Python?

สมมติว่าเรามีตัวเลข A และ B สองตัว ตอนนี้ในแต่ละการดำเนินการ เราสามารถเลือกตัวเลขตัวใดตัวหนึ่งและเพิ่มได้ 1 หรือลดลง 1 เราต้องหาจำนวนการดำเนินการขั้นต่ำที่เราต้องการเพื่อให้ตัวหารร่วมมากสุด ระหว่าง A และ B ไม่ใช่ 1

ดังนั้น หากอินพุตเป็น A =8, B =9 เอาต์พุตจะเป็น 1 เนื่องจากเราเลือก 9 ได้ จากนั้นจึงเพิ่มเป็น 10 ดังนั้น 8 และ 10 จึงไม่เท่ากัน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• ถ้า gcd ของ a และ b ไม่เหมือนกับ 1 แล้ว

  • คืนค่า 0

• ถ้า a เป็นคู่หรือ b เป็นคู่ แล้ว

  • กลับ 1

• มิฉะนั้น

  • ถ้า gcd ของ a + 1 และ b ไม่เหมือนกับ 1 หรือ gcd ของ a - 1 และ b ไม่เหมือนกับ 1 หรือ gcd ของ a และ b - 1 ไม่เหมือนกับ 1 หรือ gcd ของ 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