Hướng dẫn giải của [CSES 1081] Common Divisors
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.
Đầu tiên ta tạo một vector count để lưu số lần xuất hiện của mỗi số từ ~1~ đến ~N~ trong dữ liệu vào.
Sau đó, ta thực hiện một tìm kiếm theo kiểu sàng Eratosthenes để xác định ước số lớn nhất chia hết ít nhất hai số. Quá trình tìm kiếm mất ~O(N \log N)~ thời gian, vì tổng số bước tương ứng với tổng điều hòa
$$N + N/2 + N/3 + \dots = O(N \log N).$$
Do đó, giải pháp chạy trong ~O(n + N \log N)~ thời gian.
#include <iostream>
#include <vector>
using namespace std;
const int N = 1000000;
int main() {
vector<int> count(N + 1);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
count[x]++;
}
for (int i = N; i >= 1; i--) {
int total = 0;
for (int j = i; j <= N; j += i) {
total += count[j];
}
if (total >= 2) {
cout << i << "\n";
break;
}
}
}
Chương trình tham khảo
#include <iostream>
#include <vector>
using namespace std;
const int N = 1000000;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<int> count(N + 1);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
count[x]++;
}
for (int i = N; i >= 1; i--) {
int total = 0;
for (int j = i; j <= N; j += i) {
total += count[j];
}
if (total >= 2) {
cout << i << "\n";
break;
}
}
}
Bình luận