HSG THPT Hải Phòng 2021 - Bài 2
View as PDF
Số ~x~ là số siêu nguyên tố tiềm năng khi thỏa mãn đồng thời 3 điều kiện sau:
~x~ là số nguyên tố;
Thêm vào bên phải số ~x~ một chữ số ~\in \{0,1,...,9\}~, số thu được là số nguyên tố;
Khi lần lượt xóa đi từng chữ số bên phải của ~x~, số thu được vẫn là số nguyên tố.
Ví dụ : Số ~x=313~ là số siêu nguyên tố tiềm năng vì:
~x~ là số nguyên tố;
Thêm vào bên phải số ~x~ chữ số ~7~, ta thu được ~3137~ cũng là số nguyên tố;
Khi lần lượt xóa đi các chữ số bên phải của ~x~, ta thu được ~31;3~ là các số nguyên tố.
Cho dãy gồm ~N~ số nguyên dương ~a_1,a_2,\ldots,a_n~ và ~T~ bộ (~u,v~) (~1\le u < v \le n~). Hãy đếm số lượng số siêu nguyên tố tiềm năng trong đoạn ~a_u,a_{u+1},\ldots,a_v~.
Input
Dữ liệu vào gồm:
Dòng 1: Chứa số nguyên dương ~N~;
Dòng 2: Chứa ~N~ số nguyên dương ~a_1,a_2,\ldots,a_n~;
Dòng 3: Chứa số nguyên dương ~T~ là số lượng câu hỏi;
~T~ dòng tiếp theo, dòng thứ ~i~ chứa 2 số nguyên dương (~u,v~) (~1\le u < v \le n~) ứng với câu hỏi thứ ~i~ là trong đoạn ~a_u,a_{u+1},\ldots,a_v~ có bao nhiêu số siêu nguyên tố tiềm năng.
Output
Ghi ra trên ~T~ dòng, dòng thứ ~i~ là đáp án câu hỏi ~i~ trong file dữ liệu vào.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~25\%~ | ~T = 1, N \le 100,a_i \le 10^3~ |
| 2 | ~35\%~ | ~T \le 10, 101 \le N \le 10^3,a_i \le 10^8~ |
| 3 | ~40\%~ | ~T \le 10^5, 10^3 + 1 \le N \le 10^5,a_i \le 10^6~ |
Sample Input 1
6
59 12 57 53 23 313
3
1 3
2 5
3 6
Sample Output 1
1
1
2
Notes
Các số siêu nguyên tố tiềm năng trong dãy ban đầu là: ~59~,~23~,~313~.
Với câu hỏi 1, đoạn ~a_1,a_2,a_3~ có 1 số siêu nguyên tố tiềm năng là ~a_1=59~.
Comments
oh me
fact: bài này khỏi sàng vẫn ổn :D
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
code này sao ac nổi
Các bạn có thể chia subtask ra làm cũng AC được nha
Sàng nguyên tố.
This comment is hidden due to too much negative feedback. Show it anyway.