Greatest Common Divisor

Q: Độ phức tạp thời gian của thuật toán Euclid là gì?

O(log(min(a, b))) bước và không gian O(1) . Đầu vào khiến thuật toán chạy chậm nhất là các số Fibonacci liên tiếp: 701408733 và 433494437 cần 42 bước, hoặc 43 bước nếu số nhỏ hơn đứng trước, nhiều nhất trong mọi cặp số có giá trị đến 10^9 .

Q: Ước chung lớn nhất của hai số nguyên tố cùng nhau là bao nhiêu?

Đó là 1 : hai số nguyên tố cùng nhau khi và chỉ khi chúng không có thừa số nguyên tố chung. Hai số nguyên tố khác nhau luôn nguyên tố cùng nhau, và hai số nguyên liên tiếp như 8 và 9 cũng vậy.

Người mớiToán và mô phỏng

+10

Bạn nhận được hai số nguyên dương a và b. Hãy trả về ước chung lớn nhất của chúng, tức là số nguyên lớn nhất chia hết cả hai số.

Ví dụ, các số chia hết cả 8 và 12 là 1, 2 và 4, vậy đáp án là 4.

Hàm

gcd(a: integer, b: integer) → integer

ainteger: số nguyên dương đầu tiên
binteger: số nguyên dương thứ hai
Trả vềinteger: số nguyên lớn nhất chia hết cả a và b

Ràng buộc

1 ≤ a ≤ 10⁹
1 ≤ b ≤ 10⁹

Ví dụ

Đầu vào: a = 12b = 18
Đầu ra: 6
Giải thích: Các ước số của 12 là 1, 2, 3, 4, 6 và 12; các ước số của 18 là 1, 2, 3, 6, 9 và 18. Số lớn nhất có trong cả hai danh sách là 6.

Đầu vào: a = 17b = 5
Đầu ra: 1
Giải thích: 17 và 5 đều là số nguyên tố và khác nhau, nên ước số duy nhất mà chúng có chung là 1.

Đầu vào: a = 42b = 42
Đầu ra: 42
Giải thích: Một số chia hết cho chính nó, và không có số nào lớn hơn 42 có thể chia hết cho 42, nên ước chung lớn nhất của 42 và 42 là 42.

Câu hỏi mở rộng

Bạn có thể mở rộng thuật toán Euclid để trả về cả hai số nguyên x và y sao cho a × x + b × y = gcd(a, b) không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Thử từng ứng viên một sẽ hiệu quả với các số nhỏ, nhưng hai số gần 10^9 không có thừa số chung buộc bạn phải thử đến một tỷ lần. Quy tắc Euclid gcd(a, b) = gcd(b, a % b) thu nhỏ cặp số nhanh đến mức không có cặp số nào đến 10^9 cần quá 43 bước.

Đếm ngược từ số nhỏ hơn

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Ước chung không thể lớn hơn số nhỏ hơn. Bắt đầu với d bằng min(a, b) rồi giảm đi một đơn vị cho đến khi nó chia hết cả hai số. Vì bạn bắt đầu từ số lớn nhất, số đầu tiên tìm được chính là ước chung lớn nhất, và vòng lặp luôn dừng ở 1. Với 12 và 18, bạn thử từ 12 giảm xuống 7 rồi dừng ở 6.

Mỗi ứng viên cần thử một lần. Với hai số nguyên tố 999999937 và 999999929, kết quả là 1, nên vòng lặp chạy gần 10^9 lần.

Thuật toán

Đặt d bằng giá trị nhỏ hơn trong a và b.
Trong khi a % d hoặc b % d khác 0, hãy trừ 1 khỏi d.
Trả về d.

def gcd(a, b):
    d = min(a, b)
    while a % d != 0 or b % d != 0:
        d -= 1
    return d

Thuật toán Euclid

Ý tưởng

Viết a = q × b + r với r = a % b. Một số chia hết cho a và b cũng chia hết cho r = a - q × b, và một số chia hết cho b và r cũng chia hết cho a = q × b + r. Vì vậy, (a, b) và (b, r) có cùng các ước chung, và có cùng ước chung lớn nhất.

Lặp lại cho đến khi b bằng 0. Mọi số đều chia hết cho 0, vì vậy gcd(a, 0) = a. Với 12 và 18, các cặp lần lượt là (12, 18), (18, 12), (12, 6), (6, 0), và đáp án là 6. Khi a nhỏ hơn, bước đầu tiên sẽ đổi chỗ hai số, nên bạn không cần sắp xếp.

Cứ sau hai bước, số lớn hơn giảm ít nhất một nửa, vì vậy vòng lặp chạy O(log(min(a, b))) lần.

Thuật toán

Khi b khác 0, hãy tính r = a % b.
Đặt a = b và b = r.
Khi b đạt 0, trả về a.

def gcd(a, b):
    # gcd(a, b) == gcd(b, a % b), and gcd(a, 0) == a.
    while b != 0:
        a, b = b, a % b
    return a

Lỗi thường gặp và trường hợp biên

Cập nhật sai thứ tự. a = b rồi đến b = a % b sẽ tính b % b, kết quả luôn là 0. Hãy lưu số dư (remainder) trước hoặc gán cả hai giá trị cùng lúc.
Trả về b khi vòng lặp (loop) kết thúc. Lúc đó, b bằng 0.
Dừng đếm ngược ở 2. Khi đó, các cặp nguyên tố cùng nhau như 17 và 5 sẽ không tìm được đáp án.
Dùng phép trừ lặp lại thay vì phép lấy số dư. Khi đó, gcd(10^9, 1) cần một tỷ phép trừ, còn một phép % là đủ.

Câu hỏi thường gặp3

Độ phức tạp thời gian của thuật toán Euclid là gì?

O(log(min(a, b))) bước và không gian O(1). Đầu vào khiến thuật toán chạy chậm nhất là các số Fibonacci liên tiếp: 701408733 và 433494437 cần 42 bước, hoặc 43 bước nếu số nhỏ hơn đứng trước, nhiều nhất trong mọi cặp số có giá trị đến 10^9.

Sự khác nhau giữa GCD và LCM là gì?

Ước chung lớn nhất là số lớn nhất chia hết cho cả hai đầu vào; bội chung nhỏ nhất là số nhỏ nhất chia hết cho cả hai đầu vào. Chúng liên hệ với nhau qua gcd(a, b) × lcm(a, b) = a × b, vì vậy bội chung nhỏ nhất là a / gcd(a, b) × b.

Ước chung lớn nhất của hai số nguyên tố cùng nhau là bao nhiêu?

Đó là 1: hai số nguyên tố cùng nhau khi và chỉ khi chúng không có thừa số nguyên tố chung. Hai số nguyên tố khác nhau luôn nguyên tố cùng nhau, và hai số nguyên liên tiếp như 8 và 9 cũng vậy.

def gcd(a, b):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

a = 12
b = 18

Đầu ra mong đợi