NGUYENTO – Nguyên tố

Buổi 15 — Prefix Sum & Difference Array Buổi 57 — Sàng & Euler Totient Number Theory prefix-sum
Points
60
AC Rate
20.0%
Time limit
1.0 s
Memory limit
256M
Group
number
Submissions

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:

  1. $x$ là số nguyên tố;
  2. 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$.
Draft saved