Số họcƯớc/Bội chung
Cho hai số nguyên không âm a và b, tính ước chung lớn nhất (GCD) của chúng.
Thuật toán Euclid: gcd(a, b) = gcd(b, a mod b), dừng khi b = 0.
Ràng buộc
0 <= a, b <= 10^9
Ví dụ
a | b | Kết quả |
|---|---|---|
12 | 18 | 6 |
48 | 36 | 12 |
45 phút, không xem lời giải. Vừa viết vừa nói ra hướng tiếp cận, như phỏng vấn thật.
Cho hai số nguyên không âm a và b, tính ước chung lớn nhất (GCD) của chúng.
Thuật toán Euclid: gcd(a, b) = gcd(b, a mod b), dừng khi b = 0.
0 <= a, b <= 10^9a | b | Kết quả |
|---|---|---|
12 | 18 | 6 |
48 | 36 | 12 |