Hướng dẫn giải của Đếm số
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
Số có đúng 2 ước nguyên dương là số nguyên tố. Cần đếm số phần tử nguyên tố trong dãy, và số lần xuất hiện của từng số nguyên tố.
Sub 1: Thử chia từng số — ~O(n \sqrt{A})~, dùng khi ~n \le 1000~
Với mỗi phần tử, kiểm tra nguyên tố bằng cách thử chia đến căn bậc hai. Đếm các số nguyên tố bằng bảng map.
Nếu chỉ nộp sub này: đúng 16/20 test.
Sub 2: Sàng Eratosthenes — ~O(A \log \log A)~
Sàng nguyên tố đến giá trị lớn nhất trong dãy rồi tra cứu mỗi phần tử trong O(1). Với ~n~ đến ~10^7~ cần đọc nhập nhanh (fread) và dùng mảng đếm thay cho map, nếu không sẽ quá giờ.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Kết quả: dòng đầu là tổng số phần tử nguyên tố; mỗi dòng sau là một số nguyên tố kèm số lần xuất hiện, theo thứ tự tăng dần. Dữ liệu ~n \le 1000~ dùng sub 1, còn lại dùng sub 2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> A;
// Đọc số nguyên nhanh (n có thể đến 10^7 số)
static char buf[1 << 25];
size_t bl = 0, bp = 0;
int readInt() {
while (true) {
if (bp == bl) { bl = fread(buf, 1, sizeof(buf), stdin); bp = 0; if (bl == 0) return 0; }
if (buf[bp] >= '0' && buf[bp] <= '9') break;
bp++;
}
int x = 0;
while (true) {
if (bp == bl) { bl = fread(buf, 1, sizeof(buf), stdin); bp = 0; if (bl == 0) break; }
if (buf[bp] < '0' || buf[bp] > '9') break;
x = x * 10 + (buf[bp++] - '0');
}
return x;
}
// Sub 1: kiểm tra nguyên tố bằng chia thử đến căn bậc hai, O(n * sqrt(max A)). Dùng khi n <= 1000.
bool isPrimeTrial(int x) {
if (x < 2) return false;
for (long long d = 2; d * d <= x; d++)
if (x % d == 0) return false;
return true;
}
void sub1() {
map<int, int> cnt;
long long total = 0;
for (int x : A)
if (isPrimeTrial(x)) { cnt[x]++; total++; }
printf("%lld\n", total);
for (auto& kv : cnt) printf("%d %d\n", kv.first, kv.second);
}
// Sub 2: sàng Eratosthenes đến max A, đếm số lần xuất hiện bằng mảng đếm, duyệt tăng dần để in. Dùng cho n lớn.
void sub2() {
int mx = 2;
for (int x : A) mx = max(mx, x);
vector<char> comp(mx + 1, 0);
comp[0] = comp[1] = 1;
for (long long i = 2; i * i <= mx; i++)
if (!comp[i])
for (long long j = i * i; j <= mx; j += i) comp[j] = 1;
vector<int> cnt(mx + 1, 0);
long long total = 0;
for (int x : A)
if (!comp[x]) { cnt[x]++; total++; }
string out = to_string(total) + "\n";
for (int v = 2; v <= mx; v++)
if (cnt[v]) out += to_string(v) + " " + to_string(cnt[v]) + "\n";
fputs(out.c_str(), stdout);
}
int main() {
n = readInt();
A.resize(n);
for (int i = 0; i < n; i++) A[i] = readInt();
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận