Hướng dẫn giải của TIN10_LOOP22: Ước chung
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 N, M (đến 10^9). Liệt kê tất cả các ước chung của N và M theo thứ tự tăng dần, cách nhau một khoảng trắng.
Sub 1: Vét cạn — ~O(min(N, M))~
Thử lần lượt mọi số d từ 1 đến min(N, M); nếu d chia hết cả N và M thì d là ước chung và in ra. Đúng với mọi test nhưng chậm khi N, M lớn: đạt 14/20 test (các test lớn bị quá giờ).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n, m;
cin >> n >> m;
// Vét cạn: thử mọi số d từ 1 đến min(n, m), d là ước chung nếu chia hết cả n và m
long long mn = min(n, m);
bool first = true;
for (long long d = 1; d <= mn; d++) {
if (n % d == 0 && m % d == 0) {
if (!first) cout << ' ';
cout << d;
first = false;
}
}
cout << '\n';
return 0;
}
Sub 2: Tìm ước của ƯCLN — ~O(√N)~
Ước chung của N và M chính là ước của g = ƯCLN(N, M). Chỉ cần thử d đến √g: với mỗi d chia hết g thì cả d và g/d đều là ước. Lưu ý không in trùng khi d = g/d và phải ghép hai danh sách theo thứ tự tăng dần. Dùng long long để tránh tràn khi nhân d·d. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n, m;
cin >> n >> m;
// Ước chung của n và m chính là ước của g = ƯCLN(n, m)
long long g = __gcd(n, m);
// Chỉ cần thử d đến căn(g): mỗi cặp (d, g/d) cho hai ước
vector<long long> small, large;
for (long long d = 1; d * d <= g; d++) {
if (g % d == 0) {
small.push_back(d);
if (d != g / d) large.push_back(g / d);
}
}
// Ghép hai danh sách theo thứ tự tăng dần
vector<long long> res = small;
for (int i = (int)large.size() - 1; i >= 0; i--) res.push_back(large[i]);
for (size_t i = 0; i < res.size(); i++) {
if (i) cout << ' ';
cout << res[i];
}
cout << '\n';
return 0;
}
Bình luận