มีจำนวน A, B ออปปอเรชัน: เลือก A หรือ B แล้ว +1 หรือ -1 หาออปปอเรชันน้อยที่สุดให้ GCD(A,B) ≠ 1
ตัวอย่าง: A=8, B=9 → 1 (9→10, GCD(8,10)=2)
สังเกต
- ถ้า GCD ≠ 1 อยู่แล้ว → 0
- ถ้าหนึ่งในสองเป็นเลขคู่ → 1 (เลขคู่มีตัวหาร 2)
- ทั้งคู่คี่: ลอง +1/-1 แต่ละตัว ดูว่า GCD ≠ 1 ได้ไหม → 1
- มิฉะนั้น → 2 (เสมอทำได้ภายใน 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, B = 8, 9
print(ob.solve(A, B)) # 1
อินพุต
8, 9
เอาต์พุต
1
