Đếm phép toán tối thiểu làm 2 số không nguyên tố cùng nhau trong Python

Cho 2 số A, B. Mỗi phép: chọn 1 số, +1 hoặc -1. Tìm số phép tối thiểu để gcd(A, B) != 1.

Ví dụ: A=8, B=9 → 1 (9→10, gcd(8,10)=2).

Logic: Nếu đã không nguyên tố cùng nhau → 0. Nếu có số chẵn → 1 (làm cả 2 chẵn). Ngược lại (cả 2 lẻ), kiểm tra 4 hướng ±1: nếu tạo ra cặp không nguyên tố cùng nhau → 1, else → 2 (luôn có thể làm cả 2 chẵn trong 2 bước).

Ví dụ triển khai

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
        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
        return 2

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

Đầu vào

8, 9

Đầu ra

1