Hướng dẫn giải của LIST17: Các số nguyên tố
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
Lấy các số nguyên tố trong dãy, sắp xếp giảm dần theo tổng chữ số và in số lượng cùng dãy kết quả.
Lưu ý quy ước: các số có cùng tổng chữ số giữ nguyên thứ tự xuất hiện trong dãy (khớp ví dụ: 17 đứng trước 71); số âm, 0 và 1 không phải số nguyên tố.
Sub 1: Thử chia và chọn dần — ~O(n \sqrt{M} + k^2)~ với ~k~ số nguyên tố, dùng khi ~n \le 1000~
Kiểm tra nguyên tố bằng thử chia rồi sắp xếp chọn dần theo tổng chữ số giảm dần, giữ thứ tự ban đầu khi bằng nhau.
Nếu chỉ nộp sub này: đúng 14/20 test.
Sub 2: Sàng và sắp xếp — ~O(M \log \log M + k \log k)~, dùng khi mọi trường hợp còn lại
Sàng số nguyên tố đến ~M = \max|A_i|~, lấy các số dương là nguyên tố, rồi sắp xếp ổn định theo tổng chữ số giảm dần.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Đề không chia subtask. Số âm không được coi là số nguyên tố.
Chương trình đọc ~n~ và dãy. Nếu ~n \le 1000~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a;
// Kiem tra nguyen to bang thu chia (dung cho sub 1)
bool laNguyenTo(long long x) {
if (x < 2) return false;
for (long long d = 2; d * d <= x; d++)
if (x % d == 0) return false;
return true;
}
int tongChuSo(long long x) {
int s = 0;
while (x > 0) { s += x % 10; x /= 10; }
return s;
}
// Sub 1: loc so nguyen to bang thu chia, roi chon sap xep giam dan theo tong chu so. Dung khi n <= 1000
void sub1() {
vector<long long> p;
for (int i = 0; i < n; i++)
if (laNguyenTo(a[i])) p.push_back(a[i]);
// Selection sort giam dan theo tong chu so, giu thu tu ban dau khi bang nhau
int m = p.size();
for (int i = 0; i < m; i++) {
int best = i;
for (int j = i + 1; j < m; j++)
if (tongChuSo(p[j]) > tongChuSo(p[best])) best = j;
rotate(p.begin() + i, p.begin() + best, p.begin() + best + 1);
}
cout << m << "\n";
for (int i = 0; i < m; i++) cout << p[i] << (i + 1 < m ? ' ' : '\n');
}
// Sub 2: sang nguyen to den max|A| roi stable_sort giam dan theo tong chu so
void sub2() {
long long M = 2;
for (int i = 0; i < n; i++) M = max(M, llabs(a[i]));
vector<bool> comp(M + 1, false);
comp[0] = comp[1] = true;
for (long long i = 2; i * i <= M; i++)
if (!comp[i])
for (long long j = i * i; j <= M; j += i) comp[j] = true;
vector<long long> p;
for (int i = 0; i < n; i++)
if (a[i] >= 2 && !comp[a[i]]) p.push_back(a[i]);
stable_sort(p.begin(), p.end(), [](long long x, long long y) { return tongChuSo(x) > tongChuSo(y); });
int m = p.size();
cout << m << "\n";
for (int i = 0; i < m; i++) cout << p[i] << (i + 1 < m ? ' ' : '\n');
}
int main() {
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận