Đếm số tọa độ nguyên trên đoạn thẳng giữa hai điểm trong Python

Cho hai điểm (p1,q1) và (p2,q2). Đếm số điểm có tọa độ nguyên (cả x và y đều nguyên) nằm trên đoạn thẳng nối hai điểm (không tính hai đầu).

Ví dụ: (3,3) và (6,6) → 2 điểm: (4,4) và (5,5).

Giải thuật

• Số điểm nguyên trên đoạn thẳng (trừ hai đầu) = gcd(|x2-x1|, |y2-y1|) - 1.
• Tính gcd bằng thuật toán Euclid.

Ví dụ mã Python

def gcd_find(x, y):
    if y == 0:
        return x
    return gcd_find(y, x % y)

def solve(p1, q1, p2, q2):
    return gcd_find(abs(p2 - p1), abs(q2 - q1)) - 1

print(solve(3, 3, 6, 6))  # Output: 2

Đầu vào

3,3,6,6

Đầu ra

2