Ước chung lớn nhất (GCD) bằng thuật toán Euclid
Khi rút gọn phân số, đồng bộ chu kỳ tác vụ hoặc chia đều tài nguyên, ta luôn cần tìm ước chung lớn nhất (GCD) của hai số. Cách duyệt từng ước để tìm GCD tốn O(min(a,b)) và sẽ quá…
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: python-basics, loops, modulo.
Nội dung đề bài
Mô tả bài toán
Khi rút gọn phân số, đồng bộ chu kỳ tác vụ hoặc chia đều tài nguyên, ta luôn cần tìm ước chung lớn nhất (GCD) của hai số. Cách duyệt từng ước để tìm GCD tốn O(min(a,b)) và sẽ quá chậm với số lớn. Thuật toán Euclid dựa trên hệ thức gcd(a, b) = gcd(b, a bmod b) chỉ mất O(log min(a,b)).
Yêu cầu
Đọc từ stdin hai số nguyên a và b trên cùng một dòng, cách nhau bởi dấu cách. In ra ước chung lớn nhất của |a| và |b|.
Quy ước: gcd(0, 0) = 0; gcd(x, 0) = |x|.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không truyền lời nhắc vào
input(). Lời nhắc sẽ bị in vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
Một dòng chứa hai số nguyên a, b cách nhau bởi dấu cách.
Output
Một số nguyên duy nhất là GCD của |a| và |b|.
Ràng buộc
- -109 ≤ a, b ≤ 109.
- Thời gian chạy tối đa: 1000ms. Giới hạn bộ nhớ: 256MB.
Ví dụ 1
Input
12 18Output
6
$\gcd(12,18)=\gcd(18,12)=6$.Ví dụ 2
Input
0 0Output
0
Cả hai số đều bằng 0; theo quy ước, kết quả là 0.Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.