Hướng dẫn giải của F01: Phân số tối giản
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho hai số nguyên dương a và b, cần in ra tử số và mẫu số của phân số a/b sau khi rút gọn.
Cách làm
Tìm ước chung lớn nhất g của a và b bằng thuật toán Euclid: lặp lấy số dư cho đến khi số dư bằng 0. Sau đó chia cả a và b cho g rồi in ra kết quả.
#include <bits/stdc++.h>
using namespace std;
// Tìm ước chung lớn nhất bằng thuật toán Euclid
int gcd_so(int x, int y) {
while (y != 0) {
int r = x % y;
x = y;
y = r;
}
return x;
}
int main() {
int a, b;
cin >> a >> b;
int g = gcd_so(a, b);
// Chia cả tử và mẫu cho ước chung lớn nhất
cout << a / g << " " << b / g << "\n";
return 0;
}
Bình luận