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
prefix
ko cần sàng mà vẫn AC ?:))
sàng sử dụng bitset
Cho em hỏi là
#define ham_nhanh inline __attribute__((always_inline))đi thi được dùng 0 ạ? Em cảm ơn ạCho em hỏi là
#define ham_nhanh inline __attribute__((always_inline))đi thi được dùng 0 ạ? Em cảm ơn ạhttps://ideone.com/jaU0JO mọi người đánh giá code này của em cần thêm gì để tối ưu ạ
Bài này dùng sàng mà bị quá bộ nhớ thì phải làm sao ạ?
Vậy thì b đừng sàng nữa, thử nghĩ cách khác xem sao?
Hint
tổng tiền tố
Sub 3 để 1e6 nhưng phải 8e6 mới AC ?
Sub3 nhưng bị dính 1e8 từ sub2 á
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.