Hướng dẫn giải của LOOP20: Liệt kê ước chẵ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
Liệt kê các ước chẵn của N, không kể chính N; nếu không có thì in 0. N ≤ 10^9 nên không thể thử đến N.
Sub 1: Vét cạn — ~O(N)~
Thử từng ước i từ 1 đến N − 1, in các i chia hết N và là số chẵn. Đạt 14/20 test (6 test còn lại quá giờ).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
// Vét cạn: thử từng ước i từ 1 đến N-1, in các ước chẵn theo thứ tự tăng dần
bool found = false;
for (long long i = 1; i < n; i++) {
if (n % i == 0 && i % 2 == 0) {
cout << i << " ";
found = true;
}
}
if (!found) cout << 0;
cout << "\n";
return 0;
}
Sub 2: Duyệt đến căn bậc hai — ~O(√N + k log k)~
Mỗi cặp ước (i, N/i) với i ≤ √N được xét; ước chẵn được lưu lại (loại bỏ N và tránh lưu trùng khi i = N/i), sau đó sắp xếp tăng dần để in. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
// Tìm các ước theo cặp (i, N/i) với i <= căn(N), lưu lại các ước chẵn khác N
vector<long long> res;
for (long long i = 1; i * i <= n; i++) {
if (n % i == 0) {
long long j = n / i;
if (i % 2 == 0 && i != n) res.push_back(i);
if (j != i && j % 2 == 0 && j != n) res.push_back(j);
}
}
if (res.empty()) {
cout << 0 << "\n";
return 0;
}
sort(res.begin(), res.end()); // các ước được in theo thứ tự tăng dần
for (size_t k = 0; k < res.size(); k++) {
if (k) cout << " ";
cout << res[k];
}
cout << "\n";
return 0;
}
Bình luận