Hướng dẫn giải của [VTT Q4 Contest 06] Bài 3: Số nguyên tố đối xứng [SYMPRIME]
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
Với số nguyên tố ~n~, cần biết số nguyên tố kề trước ~p~ và kề sau ~s~ rồi kiểm tra ~p + s = 2n~. Chú ý ~n = 2~ không có số kề trước nên luôn là NO.
Sub 1: Thử từng số — dùng khi ~t, n \le 1000~
Với mỗi truy vấn, lùi từ ~n-1~ về đến khi gặp số nguyên tố, tiến từ ~n+1~ đến khi gặp số nguyên tố (kiểm tra nguyên tố bằng chia thử đến căn). Với miền nhỏ rất nhanh. Nếu chỉ nộp sub này: đúng 20/20 test khi ép chạy riêng (máy chấm cục bộ dễ dãi), nhưng ngưỡng chỉ phủ subtask 1; trong chương trình hoàn chỉnh sub này chỉ xử lý 1 test.
Sub 2: Sàng Eratosthenes — ~O(M \log \log M + t)~
Sàng một lần đến hơn ~10^6~ (số nguyên tố kế tiếp sau ~10^6~ là ~1000003~, nên sàng đến ~1.1 \cdot 10^6~). Quét xuôi/ngược để lưu số nguyên tố kề trước và kề sau của mọi số, mỗi truy vấn trả lời ~O(1)~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Main đọc các truy vấn; nếu ~t \le 1000~ và mọi ~n \le 1000~ thì gọi sub1, ngược lại sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
const int MX = 1100000;
int t;
int q[100005];
bool comp[MX + 5];
int prv[MX + 5], nxt[MX + 5];
bool isPrime(int x) {
if (x < 2) return false;
for (int d = 2; d * d <= x; d++) if (x % d == 0) return false;
return true;
}
// Sub 1: với mỗi số, tìm số nguyên tố kề trước/kề sau bằng cách thử từng số. ~O(t * khoảng cách * căn n)~
void sub1() {
for (int i = 0; i < t; i++) {
int n = q[i];
int p = n - 1, s = n + 1;
while (p >= 2 && !isPrime(p)) p--;
while (!isPrime(s)) s++;
if (p >= 2 && isPrime(n) && p + s == 2 * n) cout << "YES\n";
else cout << "NO\n";
}
}
// Sub 2: sàng Eratosthenes đến hơn 10^6 một lần, lưu số nguyên tố kề trước/sau của mọi số. ~O(M log log M + t)~
void sub2() {
for (int i = 2; (long long)i * i <= MX; i++)
if (!comp[i]) for (int j = i * i; j <= MX; j += i) comp[j] = true;
int last = 0;
for (int i = 2; i <= MX; i++) {
prv[i] = last;
if (!comp[i]) last = i;
}
last = 0;
for (int i = MX; i >= 2; i--) {
nxt[i] = last;
if (!comp[i]) last = i;
}
for (int i = 0; i < t; i++) {
int n = q[i];
if (n >= 2 && !comp[n] && prv[n] && nxt[n] && prv[n] + nxt[n] == 2 * n) cout << "YES\n";
else cout << "NO\n";
}
}
int main() {
freopen("SYMPRIME.INP", "r", stdin);
freopen("SYMPRIME.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> t;
int mx = 0;
for (int i = 0; i < t; i++) { cin >> q[i]; mx = max(mx, q[i]); }
if (t <= 1000 && mx <= 1000) sub1();
else sub2();
}
Bình luận