Hướng dẫn giải của Hộp quà (THCS KS1)
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 dãy ~n~ số nguyên dương, đếm số phần tử là số nguyên tố. Một số nguyên tố là số lớn hơn 1 chỉ có hai ước là 1 và chính nó.
Sub 1: Vét cạn — ~O(n \cdot a)~, dùng khi ~n \le 1000~ và ~a_i \le 1000~
Với mỗi số, thử chia cho mọi số từ 2 đến số đó trừ 1. Nếu không chia hết cho số nào thì là số nguyên tố. Nếu chỉ nộp sub này: đúng 40/50 test (đúng hết các test trong miền của nó, 10 test lớn bị quá giờ).
Sub 2: Sàng Eratosthenes — ~O(M \log \log M + n)~, với ~M = \max a_i \le 10^6~
Đánh dấu các hợp số trong đoạn ~[0, M]~ bằng sàng: với mỗi số ~i~ chưa bị đánh dấu, đánh dấu các bội ~i^2, i^2+i, \ldots~. Sau đó đếm các ~a_i~ chưa bị đánh dấu.
Bẫy cần chú ý: dùng long long cho ~i \cdot i~ để tránh tràn số; đánh dấu 0 và 1 là không nguyên tố.
Nếu chỉ nộp sub này: đúng 50/50 test.
Chương trình hoàn chỉnh
main đọc dữ liệu và tìm ~\max a_i~. Nếu ~n \le 1000~ và ~a_i \le 1000~ thì gọi sub1, còn lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
long long a[1000005]; // day so dung chung cho cac sub
long long maxA = 0;
// Kiem tra mot so co phai so nguyen to bang cach thu moi uoc tu 2 den x-1
bool isPrimeSlow(long long x) {
if (x < 2) return false;
for (long long d = 2; d < x; d++)
if (x % d == 0) return false;
return true;
}
// Sub 1: vet can O(n * a) - moi so thu moi uoc, dung khi n <= 1000 va a <= 1000
void sub1() {
int cnt = 0;
for (int i = 1; i <= n; i++)
if (isPrimeSlow(a[i])) cnt++;
cout << cnt << "\n";
}
// Sub 2: sang Eratosthenes tren doan [0, maxA], sau do dem - dung cho du lieu lon
void sub2() {
vector<bool> composite(maxA + 1, false); // composite[x] = true neu x khong la so nguyen to
if (maxA >= 0) composite[0] = true;
if (maxA >= 1) composite[1] = true;
for (long long i = 2; i * i <= maxA; i++)
if (!composite[i])
for (long long j = i * i; j <= maxA; j += i)
composite[j] = true;
int cnt = 0;
for (int i = 1; i <= n; i++)
if (!composite[a[i]]) cnt++;
cout << cnt << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
maxA = max(maxA, a[i]);
}
if (n <= 1000 && maxA <= 1000) sub1(); // du lieu nho: vet can cho chac
else sub2(); // du lieu lon: sang
return 0;
}
Bình luận