Hướng dẫn giải của [200 đề thầy Đức] Bài 100: Tổng các số nguyên tố đối xứng
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 các truy vấn $[l, r]$, cần tính tổng các số vừa là số nguyên tố vừa là số đối xứng (đọc xuôi và ngược giống nhau) nằm trong đoạn đó. Có tối đa $200$ truy vấn và $r \le 10^5$.
Sub 1: Vét cạn — ~O(r \sqrt{r})~ mỗi test, dùng khi ~r \le 10^4~
Với mỗi $x$ trong $[l, r]$: kiểm tra $x$ có phải số nguyên tố bằng cách thử các ước đến $\sqrt{x}$, kiểm tra $x$ có đối xứng bằng cách đảo các chữ số, rồi cộng dồn nếu thỏa cả hai.
Kết quả chấm riêng sub này: đúng 21/21 test.
Sub 2: Bảng tiền tố — ~O(1)~ mỗi test sau khi tiền xử lý ~O(M \log \log M)~, với ~M = 10^5~
Nhận xét: đáp án chỉ phụ thuộc vào đoạn $[l, r]$ nên có thể tính trước. Sàng nguyên tố đến $10^5$, đánh dấu các số vừa nguyên tố vừa đối xứng, rồi lập mảng tiền tố $\text{pre}[x]$ là tổng các số như vậy không vượt quá $x$. Đáp án của $[l, r]$ là $\text{pre}[r] - \text{pre}[l-1]$.
Bẫy cần chú ý: tổng có thể lớn, nên dùng long long; và $l - 1$ có thể bằng $0$, nên $\text{pre}[0] = 0$.
Kết quả chấm riêng sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
Chương trình sàng và lập bảng tiền tố một lần, rồi với mỗi test đọc $l, r$. Nếu $r \le 10^4$ thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub1 vẫn ăn điểm các test nhỏ nếu sub2 chưa làm kịp.
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 100000;
bool isPrimeArr[MAXV + 1]; // sàng nguyên tố (dùng cho sub 2)
long long pre[MAXV + 1]; // pre[x] = tổng các số nguyên tố đối xứng <= x (dùng cho sub 2)
long long l, r;
// Kiểm tra x có đối xứng (đọc xuôi và ngược giống nhau) không
bool isPal(long long x) {
long long rev = 0, y = x;
while (y > 0) { rev = rev * 10 + y % 10; y /= 10; }
return rev == x;
}
// Kiểm tra x có phải số nguyên tố bằng cách thử mọi ước đến căn bậc hai
bool isPrimeSlow(long long x) {
if (x < 2) return false;
for (long long d = 2; d * d <= x; d++)
if (x % d == 0) return false;
return true;
}
// Sub 1: vét cạn — với mỗi x trong [l, r], kiểm tra nguyên tố và đối xứng rồi cộng dồn
// Dùng khi r <= 10^4
void sub1() {
long long sum = 0;
for (long long x = l; x <= r; x++)
if (isPrimeSlow(x) && isPal(x)) sum += x;
cout << sum << "\n";
}
// Sub 2: sàng trước các số nguyên tố đối xứng đến 10^5, rồi lấy hiệu hai tổng tiền tố
// Mỗi test trả lời trong O(1)
void sub2() {
cout << pre[r] - pre[l - 1] << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Chuẩn bị bảng cho sub 2: sàng nguyên tố rồi tính tổng tiền tố các số nguyên tố đối xứng
fill(isPrimeArr, isPrimeArr + MAXV + 1, true);
isPrimeArr[0] = isPrimeArr[1] = false;
for (int i = 2; (long long)i * i <= MAXV; i++)
if (isPrimeArr[i])
for (int j = i * i; j <= MAXV; j += i) isPrimeArr[j] = false;
pre[0] = 0;
for (int x = 1; x <= MAXV; x++)
pre[x] = pre[x - 1] + ((isPrimeArr[x] && isPal(x)) ? x : 0);
int T;
cin >> T;
while (T--) {
cin >> l >> r;
if (r <= 10000) sub1(); // r nhỏ: vét cạn cho chắc
else sub2(); // r lớn: trả lời nhanh nhờ bảng tiền tố
}
return 0;
}
Bình luận