Kỳ thi HSG THCS tỉnh Bắc Ninh 2025-2026
Time Remaining
00:00:00
My Score
0
/
200
Rank
-
/
2
Số nguyên tố là số nguyên dương lớn hơn $1$ và có đúng hai ước số dương là $1$ và chính nó.
Một số nguyên dương $x$ được gọi là số nguyên tố đặc biệt nếu:
- $x$ là số nguyên tố;
- Số viết theo thứ tự ngược lại của các chữ số của $x$ cũng là số nguyên tố.
Ví dụ: Số $13$ là số nguyên tố đặc biệt vì $13$ và $31$ đều là số nguyên tố. Số $23$ không phải là số nguyên tố đặc biệt vì $23$ là số nguyên tố nhưng số đảo ngược là $32$ không phải là số nguyên tố ($32$ chia hết cho $2$).
Cho dãy số $A$ có $N$ phần tử nguyên $A_1, A_2, \dots, A_N$ và một số nguyên dương $Q$.
Yêu cầu
Với mỗi cặp chỉ số $L, R$ ($1 \le L \le R \le N$) trong $Q$ truy vấn, hãy đếm số lượng số nguyên tố đặc biệt trong đoạn con $A_L, A_{L+1}, \dots, A_R$.
Dữ liệu vào
- Dòng 1: Ghi hai số nguyên dương $N, Q$ ($1 \le N \le 10^6, 1 \le Q \le 10^6$).
- Dòng 2: Ghi $N$ số nguyên $A_1, A_2, \dots, A_N$ ($-10^7 \le A_i \le 10^7$).
- $Q$ dòng tiếp theo, mỗi dòng ghi hai số nguyên dương $L, R$ ($1 \le L \le R \le N$) thể hiện một đoạn truy vấn.
Kết quả ra
Gồm $Q$ dòng, mỗi dòng ghi một số nguyên là số lượng số nguyên tố đặc biệt tìm được tương ứng với truy vấn.
Giới hạn
- Subtask 1 (40% số điểm): $Q = 1, 1 \le N \le 10^3$.
- Subtask 2 (30% số điểm): $Q = 1, 1 \le N \le 10^6, 1 \le A_i \le 10^6$.
- Subtask 3 (30% số điểm): $Q \le 10^6, 1 \le N \le 10^6, -10^7 \le A_i \le 10^7$.
Ví dụ
Đầu vào:
8 3
8 3 25 7 -5 13 2 -20
1 3
2 6
6 8
Đầu ra:
1
3
2
Giải thích:
- Đoạn $A[1 \dots 3] = [8, 3, 25]$: có $1$ số nguyên tố đặc biệt là $3$.
- Đoạn $A[2 \dots 6] = [3, 25, 7, -5, 13]$: có $3$ số nguyên tố đặc biệt là $3, 7, 13$.
- Đoạn $A[6 \dots 8] = [13, 2, -20]$: có $2$ số nguyên tố đặc biệt là $13, 2$.
Sample Test 1
Sample Test 2
Sample Test 3
Comments