Hướng dẫn giải của Số nguyên tố song sinh (đề chọn HSG QG Tuyên Quang 2024)
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ố song sinh: ~P~ và ~rev(P)~ đều là số nguyên tố và ~P \ne rev(P)~. Sàng số nguyên tố đến ~10^6~, tính mảng cộng dồn ~pre[x]~ số song sinh trong ~[1, x]~, mỗi truy vấn trả lời bằng hiệu ~pre[b] - pre[a-1]~.
Sub 1: duyệt từng số — ~O((b-a) \cdot 7)~, dùng khi ~T \le 10~
Với mỗi truy vấn, kiểm tra từng số trong đoạn. Nếu chỉ nộp sub này: đúng 30/35 test (các test lớn bị quá giờ).
Sub 2: mảng cộng dồn — ~O(V + T)~
Tiền xử lý ~pre[]~ một lần rồi trả lời mỗi truy vấn trong ~O(1)~. Đúng 35/35 test.
Chương trình hoàn chỉnh
main sàng số nguyên tố và tính pre[]. Nếu ~T \le 10~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 1000000;
bool isPrime[MAXV + 1];
int pre[MAXV + 1]; // pre[x] = so so song sinh trong [1..x]
int rev(int x) {
int r = 0;
while (x > 0) { r = r * 10 + x % 10; x /= 10; }
return r;
}
// Song sinh: p nguyen to, rev(p) nguyen to, va rev(p) != p.
bool twin(int p) {
if (!isPrime[p]) return false;
int q = rev(p);
return q != p && isPrime[q];
}
// Sub 1: voi moi truy van, duyet tung so trong doan [a,b]. Dung khi T <= 10.
void sub1(const vector<pair<int, int>> &qs) {
for (auto &q : qs) {
int cnt = 0;
for (int x = q.first; x <= q.second; x++)
if (twin(x)) cnt++;
cout << cnt << "\n";
}
}
// Sub 2: tien xu ly mang cong don pre[], moi truy van tra loi trong O(1). Dung cho T lon.
void sub2(const vector<pair<int, int>> &qs) {
for (auto &q : qs) cout << pre[q.second] - pre[q.first - 1] << "\n";
}
int main() {
freopen("twins.inp", "r", stdin);
freopen("twins.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Sang so nguyen to
fill(isPrime, isPrime + MAXV + 1, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; (long long)i * i <= MAXV; i++)
if (isPrime[i])
for (int j = i * i; j <= MAXV; j += i) isPrime[j] = false;
// Cong don: pre[x]
pre[0] = 0;
for (int x = 1; x <= MAXV; x++) pre[x] = pre[x - 1] + (twin(x) ? 1 : 0);
int T;
cin >> T;
vector<pair<int, int>> qs(T);
for (int t = 0; t < T; t++) cin >> qs[t].first >> qs[t].second;
if (T <= 10) sub1(qs);
else sub2(qs);
return 0;
}
Bình luận