Hướng dẫn giải của Số đặc biệt (SPNUM) (Đề HSG 12 Phú Thọ 2022-2023)
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
Đếm số nguyên tố không vượt quá ~n~ có đúng ~k~ bit 1 trong biểu diễn nhị phân.
Sub 1: Vét cạn — ~O(n \sqrt{n})~, dùng khi ~n \le 1000~
Với mỗi ~x~ từ 2 đến ~n~, thử chia để kiểm tra nguyên tố, đếm bit 1 bằng popcount.
Nếu chỉ nộp sub này: đúng 20/20 test.
Sub 2: Sàng nguyên tố — ~O(n \log \log n)~
Sàng Eratosthenes đến ~n~, và đếm trong lúc sàng: số chưa bị đánh dấu là nguyên tố, kiểm tra popcount của nó.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu rồi chọn sub theo kích thước: dữ liệu nhỏ gọi sub 1 (vét cạn), dữ liệu lớn gọi sub cuối. Khi đi thi, nên nộp đầy đủ như vậy: nếu sub sau sai hoặc chưa kịp làm thì vẫn ăn điểm các sub trước.
#include <bits/stdc++.h>
using namespace std;
long long n, k;
bool isPrimeTrial(long long x) {
if (x < 2) return false;
for (long long i = 2; i * i <= x; i++) if (x % i == 0) return false;
return true;
}
// Sub 1: vét cạn — xét từng x từ 2 đến n, thử chia để biết nguyên tố, đếm bit 1 bằng popcount. O(n sqrt n)
void sub1() {
long long cnt = 0;
for (long long x = 2; x <= n; x++)
if (isPrimeTrial(x) && __builtin_popcountll(x) == k) cnt++;
cout << cnt << "\n";
}
// Sub 2: sàng nguyên tố đến n một lần, đếm trong lúc sàng. O(n log log n)
void sub2() {
vector<char> comp(n + 1, 0);
long long cnt = 0;
for (long long x = 2; x <= n; x++) {
if (comp[x]) continue;
if (__builtin_popcountll(x) == k) cnt++;
for (long long y = x * x; y <= n; y += x) comp[y] = 1;
}
cout << cnt << "\n";
}
int main() {
freopen("SPNUM.INP", "r", stdin);
freopen("SPNUM.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> k;
if (n <= 1000) sub1(); // dữ liệu nhỏ: vét cạn
else sub2();
return 0;
}
Bình luận