Hỏi đáp
Chia sẻ kiến thức, cùng nhau phát triển
Tìm Ước số chung của hai số nguyên dương 𝑚 và 𝑛
Ước số chung của hai số nguyên dương 𝑚 và 𝑛 là số nguyên mà cả 𝑚 và 𝑛 đều chia hết
cho nó. Trong bài toán này chỉ xét đến các ước số chung nguyên dương của 𝑚 và n.
Yêu cầu: Hãy lập trình tìm các ước số chung nguyên dương của hai số 𝑚 và 𝑛 cho trước.
Dữ liệu vào: Cho trong tệp tin văn bản USCHUNG.INP gồm hai số nguyên dương 𝑚 và 𝑛.
Kết quả ra: Ghi ra tệp tin văn bản USCHUNG.OUT gồm các ước số chung nguyên dương của
𝑚 và 𝑛 trên cùng một dòng theo thứ tự tăng dần, các số được in cách nhau một dấu cách.
Ví dụ:
USCHUNG.INP USCHUNG.OUT
4
52
1 2 4
Ràng buộc: 0 < 𝑚, 𝑛 ≤ 106;
#include
using namespace std;
int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
int main() {
// Đọc dữ liệu vào từ file
ifstream infile("USCHUNG.INP");
int m, n;
infile >> m >> n;
infile.close();
int gcd_value = gcd(m, n);
ofstream outfile("USCHUNG.OUT");
for (int i = 1; i <= gcd_value; i++) {
if (gcd_value % i == 0) {
outfile << i << " ";
}
}
outfile.close();
return 0;
}