Tìm hiệu nhỏ nhất giữa các bảng nhân dịch chuyển của hai số trong Python

Cho hai số p, q và hai giá trị dịch r, s (r,s ≥ 0). Cần tìm hiệu nhỏ nhất giữa bất kỳ hai số hạng nào trong bảng nhân dịch chuyển của p và q.

Bảng nhân dịch chuyển của p: [p+r, 2p+r, 3p+r, ...]. Tương tự cho q với dịch s.

Ví dụ: p=7, q=17, r=6, s=3 → bảng 7 dịch: [13,20,27,34,...], bảng 17 dịch: [20,37,54,...] → hiệu nhỏ nhất = 0 (tại 20).

Giải thuật (Toán học)

Hiệu giữa hai số hạng: |(k*p + r) - (m*q + s)| = |k*p - m*q + (r-s)|.

Đây là bài toán tìm khoảng cách nhỏ nhất từ (r-s) đến bội số của gcd(p,q).

• g = gcd(p, q)
• diff = |r - s| % g
• Kết quả = min(diff, g - diff)

Ví dụ

import math

def get_minimum_diff(p, q, r, s):
    g = math.gcd(p, q)
    difference = abs(r - s) % g
    return min(difference, g - difference)

p = 7
q = 17
r = 6
s = 3
print(get_minimum_diff(p, q, r, s))

Đầu vào

7,17,6,3

Đầu ra

0