Tìm ước chung và bội chung bằng thuật toán Euclid

Lan có hai cuộn dây dài 84 cm và 126 cm. Bạn muốn cắt cả hai thành những đoạn bằng nhau, dài nhất có thể và không thừa dây. Nếu thử từng độ dài từ 1 cm, Lan sẽ tìm được đáp án, nhưng cách đó chậm khi độ dài lên tới hàng tỉ. Thuật toán Euclid giúp tìm đáp án bằng một chuỗi phép chia lấy dư.

Ước chung lớn nhất là độ dài chia hết cả hai cuộn dây

Một ước (divisor) của số nguyên dương a là số nguyên dương chia hết a. Một ước chung (common divisor) của hai số chia hết cả hai số. Ước chung lớn nhất (greatest common divisor), viết gcd(a, b), là ước chung có giá trị lớn nhất.

Với hai cuộn dây của Lan, đoạn dây cần chia hết cả 84 lẫn 126. Chương trình liệt kê các độ dài phù hợp:

a, b = 84, 126
common = [d for d in range(1, min(a, b) + 1) if a % d == 0 and b % d == 0]
print(*common)
print(max(common))

1 2 3 6 7 14 21 42
42

Độ dài cuối cùng là lớn nhất. Liệt kê giúp hiểu định nghĩa, nhưng với hai số cỡ 10**9, chương trình có thể phải thử gần một tỉ giá trị. Ta cần một cách giữ nguyên đáp án trong khi giảm nhanh kích thước bài toán.

Phép chia lấy dư giữ nguyên tập ước chung

Khi chia a cho b, ta có a = q * b + r, với r = a % b và 0 <= r < b nếu b > 0. Mỗi ước chung của a và b cũng chia hết r, vì r = a - q * b. Ngược lại, mỗi ước chung của b và r cũng chia hết a = q * b + r.

Vì hai cặp có cùng tập ước chung, gcd(a, b) = gcd(b, a % b). Đây là cơ sở của thuật toán Euclid (Euclidean algorithm). Ta lặp phép thay cặp cho đến khi số thứ hai bằng 0.

Ví dụ sau in từng phép chia cho cặp 252, 105:

a, b = 252, 105
while b != 0:
    r = a % b
    print(a, b, r)
    a, b = b, r
print("gcd =", a)

252 105 42
105 42 21
42 21 0
gcd = 21

Mỗi phần dư nhỏ hơn số chia dương, nên số thứ hai giảm và vòng lặp phải dừng. Khi cặp còn (a, 0), mọi ước của a đều chia hết 0. Vì vậy gcd(a, 0) = abs(a). Theo quy ước của Python, gcd(0, 0) = 0.

Cài đặt Euclid và xử lý số âm trước vòng lặp

Hàm dưới đây đưa các đối số về không âm trước. Phép gán đồng thời dùng giá trị cũ ở vế phải để tạo cặp mới.

def gcd_euclid(a, b):
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a

for a, b in [(84, 126), (0, 25), (-18, 24), (0, 0)]:
    print(a, b, gcd_euclid(a, b))

84 126 42
0 25 25
-18 24 6
0 0 0

Nếu số thứ nhất nhỏ hơn số thứ hai, phép chia đầu tiên chỉ đổi thứ tự hai số. Không cần viết nhánh riêng để hoán đổi. Khi dùng số không âm, mỗi hai bước giảm số lớn hơn ít nhất một nửa. Do đó số bước có bậc O(log(max(a, b) + 1)), với bộ nhớ phụ O(1).

Python đã cung cấp hàm math.gcd. Cài đặt của thư viện phù hợp khi bạn cần kết quả, còn bản tự viết giúp bạn hiểu phép biến đổi.

from math import gcd

print(gcd(252, 105))
print(gcd(-18, 24))
print(gcd(0, 0))
print(gcd(30, 42, 66))

21
6
0
6

Kết quả của gcd luôn không âm. Lời gọi nhiều đối số tính ước chung của toàn bộ các số được đưa vào.

Bất biến cho biết vì sao Euclid trả về đúng kết quả

Một bất biến (invariant) là điều vẫn đúng sau mỗi lần lặp. Với Euclid, GCD của cặp hiện tại bằng GCD của cặp ban đầu. Phép thay cặp không xóa ước chung và cũng không tạo ra ước chung mới.

Xét hai số 270 và 192. Phép chia cho phần dư 78, nên mọi ước chung của 270 và 192 cũng chia hết 78. Ngược lại, một số chia hết cả 192 và 78 cũng chia hết 270. Ta lặp lại lập luận cho cặp tiếp theo.

from math import gcd
a, b = 270, 192
original = gcd(a, b)
while b:
    print(a, b, gcd(a, b) == original)
    a, b = b, a % b
print(a, b, gcd(a, b) == original)

270 192 True
192 78 True
78 36 True
36 6 True
6 0 True

Mỗi dòng hiển thị cặp hiện tại và kết quả so với GCD ban đầu. Khi số thứ hai bằng 0, số thứ nhất bằng GCD cần tìm. Lời giải nộp không cần gọi thêm gcd ở mỗi vòng; lời gọi đó chỉ giúp quan sát bất biến trong ví dụ.

Lập luận về tập ước chung giải thích kết quả đúng. Lập luận về phần dư giảm giải thích vòng lặp dừng. Cả hai đều cần thiết: một chương trình có thể dừng mà vẫn in sai, hoặc giữ được một tính chất nhưng không bao giờ dừng.

Hai số nguyên tố cùng nhau khi ước chung lớn nhất bằng 1

Hai số nguyên dương là nguyên tố cùng nhau (coprime) khi gcd(a, b) == 1. Chúng không nhất thiết đều là số nguyên tố. Chẳng hạn, 8 và 15 đều có nhiều ước, nhưng không có ước chung nào lớn hơn 1.

from math import gcd

pairs = [(8, 15), (9, 15), (1, 42), (7, 7)]
for a, b in pairs:
    print(a, b, gcd(a, b) == 1)

8 15 True
9 15 False
1 42 True
7 7 False

Phép kiểm tra này chỉ cần một lần tính gcd cho mỗi cặp. Với 1 000 cặp số không vượt 10**9, số bước tăng theo khoảng 1 000 lần chi phí Euclid, thay vì thử mọi ước tới 10**9 cho từng cặp.

Chia cả tử và mẫu cho GCD để rút gọn phân số

Lan có tỉ lệ 84/126 và muốn ghi ở dạng tối giản. Nếu chia cả tử lẫn mẫu cho cùng một ước chung dương, giá trị phân số không đổi. Chia cho ước chung lớn nhất loại được mọi ước chung lớn hơn 1.

from math import gcd

numerator, denominator = -84, 126
g = gcd(numerator, denominator)
print(numerator // g, denominator // g)

-2 3

Ở ví dụ này, mẫu số dương.

Một phân số có thể viết với cả tử và mẫu âm. Để so sánh và in thống nhất, ta quy định mẫu dương sau khi rút gọn. Mẫu không được bằng 0, còn tử có thể bằng 0.

from math import gcd

def reduce_fraction(a, b):
    if b == 0:
        raise ValueError("mau phai khac 0")
    g = gcd(a, b)
    a, b = a // g, b // g
    if b < 0:
        a, b = -a, -b
    return a, b

for pair in [(42, -56), (-42, -56), (0, -9)]:
    print(*reduce_fraction(*pair))

-3 4
3 4
0 1

Vì mẫu khác 0, GCD của tử và mẫu luôn dương, kể cả khi tử bằng 0. Với tử bằng 0, phép chia tạo mẫu có độ lớn bằng 1. Bước đổi dấu sau đó đưa mẫu về 1 và giữ nguyên giá trị phân số.

Chia cả tử và mẫu cho cùng số khác 0 giữ nguyên tỉ lệ. Giả sử kết quả còn một ước chung lớn hơn 1. Khi nhân ước đó với GCD đã chia, ta tìm được một ước chung lớn hơn GCD ban đầu. Điều này mâu thuẫn với định nghĩa GCD, nên phân số đã tối giản.

Bội chung nhỏ nhất kết hợp GCD với phép chia

Một bội chung (common multiple) của hai số nguyên dương chia hết cho cả hai số. Bội chung nhỏ nhất (least common multiple), viết lcm(a, b), là bội chung dương nhỏ nhất.

Hai chuông reo sau mỗi 12 và 18 phút. Thời gian hai chuông cùng reo lại là một bội chung của 12 và 18. Bội chung dương đầu tiên là lcm(12, 18).

from math import gcd

a, b = 12, 18
g = gcd(a, b)
print(a // g * b)

36

Đặt g = gcd(a, b), a = g*x và b = g*y. Hai số x, y nguyên tố cùng nhau. Một bội chung phải chứa đủ các thừa số của cả a và b, nên bội chung nhỏ nhất là g*x*y = a // g * b.

Với số âm, lấy giá trị tuyệt đối của tích. Nếu một đối số bằng 0, quy ước lcm bằng 0. Phải kiểm tra số 0 trước khi chia, vì gcd(0, 0) bằng 0.

from math import gcd

def lcm(a, b):
    if a == 0 or b == 0:
        return 0
    return abs((a // gcd(a, b)) * b)

for pair in [(12, 18), (-6, 15), (0, 7), (0, 0)]:
    print(*pair, lcm(*pair))

12 18 36
-6 15 30
0 7 0
0 0 0

Python hỗ trợ số nguyên lớn, nên không bị tràn số nguyên cố định như một số ngôn ngữ khác. Tuy vậy, tích lớn cần thêm bộ nhớ và thời gian. Chia trước giúp tránh tạo tích trung gian lớn hơn cần thiết.

Gộp GCD dần để tìm ước chung của cả dãy

Một số là ước chung của cả dãy khi nó chia hết từng phần tử. Ta có thể gộp dần: sau mỗi bước, current là GCD của các phần tử đã xét. Khi thêm x, chỉ các ước chung của current và x còn hợp lệ.

Khởi đầu current = 0 hợp lý vì gcd(0, x) = abs(x). Đoạn mã dưới đây đọc một dãy và in GCD của nó.

4
18 30 42 70

from math import gcd

n = int(input())
values = list(map(int, input().split()))
current = 0
for value in values:
    current = gcd(current, value)
print(current)

2

Với n phần tử có trị tuyệt đối không vượt A, cách này dùng n lần tính GCD. Chi phí là O(n log(A + 1)) theo số phép chia và O(1) bộ nhớ phụ, nếu xử lý từng số ngay khi đọc.

Tiền tố và hậu tố tránh tính lại toàn bộ sau mỗi lần bỏ

Giả sử cần tính GCD của dãy sau khi bỏ đúng một phần tử. Dãy [6, 12, 18, 35, 24] cho thấy rõ tác dụng của việc bỏ một số. Bỏ 35 làm GCD tăng lên 6, còn bỏ các vị trí khác vẫn để lại cả 35 và ít nhất một số chia hết cho 6.

Tiền tố (prefix) đến vị trí i gồm các phần tử trước i. Hậu tố (suffix) từ i gồm các phần tử từ i trở đi. Ta dùng khoảng nửa kín để hai mảng có một ô đệm ở mỗi đầu.

Đặt prefix[i] là GCD của các phần tử có chỉ số nhỏ hơn i. Đặt suffix[i] là GCD từ chỉ số i đến hết. Khi bỏ values[i], đáp án là gcd(prefix[i], suffix[i + 1]).

from math import gcd

values = [6, 12, 18, 35, 24]
n = len(values)
prefix = [0] * (n + 1)
suffix = [0] * (n + 1)
for i in range(n):
    prefix[i + 1] = gcd(prefix[i], values[i])
for i in range(n - 1, -1, -1):
    suffix[i] = gcd(values[i], suffix[i + 1])
for i in range(n):
    print(i, gcd(prefix[i], suffix[i + 1]))

0 1
1 1
2 1
3 6
4 1

Hai phần không chứa phần tử bị bỏ và ghép lại đúng các phần tử còn lại. Tính chất kết hợp của GCD cho phép gộp kết quả của hai phần. Ô đệm bằng 0 xử lý thống nhất cả vị trí đầu và cuối.

Với n = 200000, cách tính lại cả dãy cho từng vị trí cần gần 40 tỉ lượt gộp. Hai mảng trên chỉ cần khoảng 3*n lần tính GCD và O(n) ô nhớ. Với dãy chỉ có một phần tử, kết quả theo quy ước ô đệm là 0; đề phải nói rõ có cho trường hợp đó hay không.

Với dãy [6, 12, 18, 35, 24], prefix[0] không chứa phần tử nào. Tương tự, suffix[5] không chứa phần tử nào. Cả hai được đặt bằng 0 để phép gộp với phần còn lại không thay đổi GCD.

from math import gcd
values = [6, 12, 18, 35, 24]
n = len(values)
prefix = [0] * (n + 1)
suffix = [0] * (n + 1)
for i, value in enumerate(values):
    prefix[i + 1] = gcd(prefix[i], value)
for i in range(n - 1, -1, -1):
    suffix[i] = gcd(values[i], suffix[i + 1])
print("prefix", *prefix)
print("suffix", *suffix)
print("bo dau", gcd(prefix[0], suffix[1]))
print("bo cuoi", gcd(prefix[n - 1], suffix[n]))

prefix 0 6 6 6 1 1
suffix 1 1 1 1 24 0
bo dau 1
bo cuoi 1

Khi bỏ đầu, chỉ hậu tố từ chỉ số 1 còn lại. Khi bỏ cuối, chỉ tiền tố trước vị trí cuối còn lại. Công thức giống nhau ở cả hai biên, nên không cần thêm nhánh riêng.

Chỉ số trong công thức đếm từ 0. Nếu đề đánh số vị trí từ 1, hãy đổi số vị trí trước khi tra hai mảng. Nhầm quy ước đánh số khiến chương trình bỏ nhầm phần tử kế bên, dù hai mảng đã được tính đúng.

Nếu chỉ cần GCD sau một lần bỏ, một lượt gộp trực tiếp cũng đủ nhanh. Hai mảng phát huy lợi ích khi cần xét nhiều vị trí.

Đếm bội tìm cặp có GCD lớn nhất

Một kho có nhiều thanh mang số hiệu dương. Cần tìm GCD lớn nhất của hai thanh ở hai vị trí khác nhau. Nếu có 50 000 thanh, thử mọi cặp cần gần 1,25 tỉ lần tính GCD.

Giả sử mọi số hiệu không vượt quá M. Một số d là ước chung của một cặp khi ít nhất hai phần tử chia hết cho d. Ta đếm tần số ở các bội d, 2*d, 3*d cho đến M.

values = [6, 10, 15, 15]
limit = max(values)
freq = [0] * (limit + 1)
for value in values:
    freq[value] += 1
for divisor in range(limit, 0, -1):
    count = 0
    for multiple in range(divisor, limit + 1, divisor):
        count += freq[multiple]
        if count >= 2:
            break
    if count >= 2:
        print(divisor)
        break

15

Duyệt d từ M xuống 1. Giá trị đầu tiên có ít nhất hai phần tử chia hết chính là đáp án. Cặp được tìm thấy có GCD không nhỏ hơn d. Nếu GCD lớn hơn, ta đã gặp ước đó trước và dừng ở đó.

Khi freq[x] bằng 2, số x đóng góp đủ hai phần tử tại bội đầu tiên của chính nó. Khi tổng đạt 2, có thể dừng đếm bội cho ước đó. Việc dừng này giữ nguyên câu trả lời vì chỉ cần biết có ít nhất hai phần tử.

Mỗi d xét tối đa khoảng M / d bội. Tổng lượt xét có bậc O(M log M); bộ nhớ là O(M). Với M = 100000, có khoảng 1,2 triệu lượt xét bội, cộng thêm một lượt đọc dãy. Nếu giá trị lên tới một tỉ, một bảng theo giá trị không còn là lựa chọn phù hợp.

Phân biệt một giá trị với một vị trí trong bài toán cặp

Dãy [15, 15] có hai vị trí khác nhau dù chỉ có một giá trị phân biệt. Cặp này hợp lệ nếu đề chỉ yêu cầu hai vị trí khác nhau. GCD của cặp là 15, nên bảng tần số phải ghi nhận hai lần xuất hiện.

Ngược lại, nếu đề yêu cầu hai giá trị khác nhau, không được dùng hai bản sao 15 làm một cặp. Điều kiện kiểm tra cần đếm các giá trị phân biệt thay vì số vị trí. Đây là hai hợp đồng đầu vào khác nhau.

from math import gcd
values = [15, 15, 10]
by_position = []
by_value = []
for i in range(len(values)):
    for j in range(i + 1, len(values)):
        by_position.append(gcd(values[i], values[j]))
        if values[i] != values[j]:
            by_value.append(gcd(values[i], values[j]))
print("khac vi tri", max(by_position))
print("khac gia tri", max(by_value))

khac vi tri 15
khac gia tri 5

Trong ví dụ, cả hai danh sách đều không rỗng. Nếu yêu cầu giá trị khác nhau mà toàn bộ phần tử bằng nhau, đề phải quy định kết quả khi không có cặp hợp lệ. Hãy đọc kỹ quy định đó thay vì tự suy ra một đáp án.

Kiểm chứng phương pháp nhanh trên dữ liệu nhỏ

Thử mọi cặp không cần bảng đến M, nên phù hợp để đối chiếu độc lập trên dãy nhỏ. Cách đếm bội phù hợp khi n lớn và M vừa phải. Hãy đọc cả giới hạn số lượng lẫn giới hạn giá trị trước khi chọn phương pháp.

from math import gcd
values = [14, 21, 25, 35]
freq = [0] * (max(values) + 1)
for x in values:
    freq[x] += 1
answer = 0
for d in range(max(values), 0, -1):
    if sum(freq[d::d]) >= 2:
        answer = d
        break
brute = max(gcd(values[i], values[j])
            for i in range(len(values))
            for j in range(i + 1, len(values)))
print(answer, brute, answer == brute)

7 7 True

Ví dụ dùng lát cắt để minh họa trên dãy nhỏ. Với dữ liệu lớn, vòng lặp trên các bội tránh tạo thêm danh sách lát cắt ở từng ước. Chạy hai cách trên nhiều dãy nhỏ giúp phát hiện nhầm chỉ số và quên các giá trị lặp.

Lỗi thường gặp

Tóm tắt

• Euclid thay (a, b) bằng (b, a % b) mà không đổi tập ước chung.
• gcd(a, 0) bằng abs(a); Python quy ước gcd(0, 0) bằng 0.
• Hai số nguyên tố cùng nhau khi GCD của chúng bằng 1.
• Với hai số khác 0, LCM là abs((a // gcd(a, b)) * b).
• Tiền tố và hậu tố giúp trả lời GCD sau khi bỏ từng vị trí mà không duyệt lại cả dãy.

Kiểm tra nhanh

Đọc thêm

• Tài liệu Python về math.gcd, gồm quy ước với số 0.
• Tài liệu Python về math.lcm, hàm tính bội chung nhỏ nhất.