TS10 Đà Nẵng 2026 - Số nguyên tố đẹp

Điểm: 14,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 1G

Input: stdin

Output: stdout

Tác giả:

clue_

Dạng bài

Ngôn ngữ cho phép

C, C++, Java, Output Only, Pascal, PyPy, Python, ~~Scratch~~, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Một số nguyên dương ~x~ được gọi là số nguyên tố đẹp nếu thỏa mãn đồng thời 3 điều kiện sau:

~x~ là số nguyên tố;
Lần lượt bỏ đi các chữ số bên phải của số ~x~ thì phần còn lại của nó vẫn là số nguyên tố;
Thêm vào bên phải của số ~x~ một chữ số bất kì thì số thu được cũng là số nguyên tố.

Ví dụ số ~313~ là số nguyên tố đẹp, vì:

Số ~313~ là số nguyên tố;
Bỏ chữ số ~3~ được số ~31~ là số nguyên tố, bỏ tiếp chữ số ~1~ ta còn số ~3~ cũng là số nguyên tố;
Thêm số ~7~ vào sau số ~313~ ta được số ~3137~ cũng là số nguyên tố.

Yêu cầu: Cho dãy ~a~ gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^6, 1 \le i \le n)~ và ~m~ truy vấn. Mỗi truy vấn có dạng ~(u, v)~ với ý nghĩa: đếm số lượng số nguyên tố đẹp trong dãy ~a~ từ vị trí ~u~ tới ~v~.

Input

Dòng thứ nhất chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~;
Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^6, 1 \le i \le n)~;
Dòng thứ ba chứa số nguyên dương ~m~ là số lượng truy vấn ~(1 \le m \le 10^5)~;
~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u, v~ ~(1 \le u \le v \le n)~.

Output

Gồm ~m~ dòng, mỗi dòng theo thứ tự của truy vấn ghi ra số lượng số nguyên tố đẹp tìm được.

Scoring

Subtask	Điểm	Ràng buộc
1	~70\%~	~1 \le a_i \le 10^3, 1 \le n \le 10^3, 1 \le m \le 10^3~
2	~30\%~	Không có ràng buộc gì thêm

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ó ~1~ số nguyên tố đẹp là ~59~ trong đoạn từ ~1~ đến ~3~.
Có ~1~ số nguyên tố đẹp là ~23~ trong đoạn từ ~2~ đến ~5~.
Có ~2~ số nguyên tố đẹp là ~23~ và ~313~ trong đoạn từ ~3~ đến ~6~.

Bình luận

Hãy đọc nội quy trước khi bình luận.

OtsgrS561 đã bình luận lúc 25, Tháng 8, 2026, 4:11

#include <bits/stdc++.h>
#define int long long
using namespace std;
const unordered_set<int> sodep = {
    2, 3, 5, 7, 23, 29, 31, 37, 59, 71, 73, 79, 233, 239, 293, 311, 313, 373, 379, 
    593, 719, 733, 739, 2333, 2339, 2399, 2939, 3119, 3137, 3733, 3739, 5939, 
    7193, 7333, 7393, 23399, 23993, 29399, 37337, 37339, 59393, 59399, 71933, 
    73939, 233993, 239933, 293999, 373379, 593933, 739391, 739393
}; 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n + 1), f(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        int ok = sodep.count(a[i]) ? 1 : 0;
        f[i] = f[i - 1] + ok;
    }
    int m;
    cin >> m;
    while (m--) {
        int u, v;
        cin >> u >> v;
        cout << f[v] - f[u - 1] << '\n';
    }
    return 0;
}