HSG THPT Hải Phòng 2021 - Bài 2
Xem dạng 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~.
Bình luận
tổng tiền tố
Sub 3 để 1e6 nhưng phải 8e6 mới AC ?
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
oh me
fact: bài này khỏi sàng vẫn ổn :D
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
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ố.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.