Hướng dẫn giải của Đếm số nguyên tố (đề HSG 12 Phú Thọ 2025-2026)
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ố trong đoạn ~[L, R]~ có tổng chữ số chia hết cho ~k~.
Sub 1: Thử chia trực tiếp — ~O(R \sqrt{R})~, dùng khi ~R \le 10^4~
Với mỗi ~x~ trong đoạn, thử chia để kiểm tra nguyên tố, rồi tính tổng chữ số và kiểm tra chia hết cho ~k~.
Nếu chỉ nộp sub này: đúng 17/27 test.
Sub 2: Sàng nguyên tố — ~O(R \log \log R)~
Sàng nguyên tố đến ~R~ một lần, rồi đếm các số không bị đánh dấu trong ~[L, R]~ có tổng chữ số chia hết cho ~k~.
Nếu chỉ nộp sub này: đúng 27/27 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 L, R, K;
int digitSum(long long x) {
int s = 0;
while (x > 0) { s += x % 10; x /= 10; }
return s;
}
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 — với mỗi x trong [L, R], thử chia để biết nguyên tố, rồi xét tổng chữ số. O(R sqrt R)
void sub1() {
long long cnt = 0;
for (long long x = L; x <= R; x++)
if (isPrimeTrial(x) && digitSum(x) % K == 0) cnt++;
cout << cnt << "\n";
}
// Sub 2: sàng nguyên tố đến R một lần, rồi đếm trên đoạn [L, R]. O(R log log R)
void sub2() {
vector<char> comp(R + 1, 0);
for (long long i = 2; i <= R; i++) {
if (comp[i]) continue;
for (long long j = i * i; j <= R; j += i) comp[j] = 1;
}
long long cnt = 0;
for (long long x = max(L, 2LL); x <= R; x++)
if (!comp[x] && digitSum(x) % K == 0) cnt++;
cout << cnt << "\n";
}
int main() {
freopen("CAU2.INP", "r", stdin);
freopen("CAU2.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> L >> R >> K;
if (R <= 10000) sub1(); // dữ liệu nhỏ: thử chia trực tiếp
else sub2();
return 0;
}
Bình luận