HSG THPT Hải Phòng 2021 - Bài 2

View as PDF
Submit solution
Points: 0.10
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
bedao
Problem source:
Kỳ thi Học sinh giỏi THPT TP Hải Phòng 2021
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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

Please read the guidelines before commenting.


  • 0
    pdinhvinh815  commented on Jan. 12, 2026, 7:49 a.m. ← edit 5

    prefix


  • 0
    pdinhvinh815  commented on Jan. 12, 2026, 6:23 a.m.

    ko cần sàng mà vẫn AC ?:))


  • 0
    vominhmanh10  commented on Dec. 14, 2025, 4:56 a.m. ← edited

    sàng sử dụng bitset 

    #include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define ham_nhanh inline __attribute__((always_inline))
#define IO ios::sync_with_stdio(0); cin.tie(nullptr)
const ll maxn = 2e6 + 5, inf = 1e18;
ll n, q, p[maxn];
bitset< 10 * maxn> primes;
vector<ll> a;
void sieve() {
    primes.set();
    primes[0] = primes[1] = 0;
    int k = sqrt(10 * maxn);
    for (int i = 4; i < 10 * maxn; i += 2) primes[i] = 0;
    for (int i = 3; i <= k; i += 2) if (primes.test(i)) for (int j = i * i; j < 10 * maxn; j += i) primes[j] = 0;
}
ham_nhanh bool check(ll x) {
    if (x < 2 || 10 * x + 9 >= 10 * maxn) return 0;
    if (!primes.test(x)) return 0;
    bool ok = 0;
    for (int i = 1; i < 10; i += 2) if (primes.test(10 * x + i)) {
        ok = 1;
        break;
    }
    if (!ok) return 0;
    while (x > 0) {
        if (!primes.test(x)) return 0;
        x /= 10;
    }
    return 1;
}
int main() {
    IO;
    cin >> n; a.resize(n);
    for (ll &x : a) cin >> x;
    cin >> q;
    sieve();
    for (int i = 1; i <= n; ++i) {
        if (check(a[i - 1])) p[i] = p[i - 1] + 1;
        else p[i] = p[i - 1];
    }
    while (q--) {
        int l, r; cin >> l >> r;
        cout << p[r] - p[l - 1] << "\n";
    }
}

    • 0
      minhkhangvophuoc  commented on Jan. 2, 2026, 3:46 p.m.

      Cho em hỏi là #define ham_nhanh inline __attribute__((always_inline)) đi thi được dùng 0 ạ? Em cảm ơn ạ


    • 0
      minhkhangvophuoc  commented on Jan. 2, 2026, 3:46 p.m.

      Cho em hỏi là #define ham_nhanh inline __attribute__((always_inline)) đi thi được dùng 0 ạ? Em cảm ơn ạ


  • 0
    quangnhat123  commented on Nov. 30, 2025, 1:15 p.m.

    https://ideone.com/jaU0JO mọi người đánh giá code này của em cần thêm gì để tối ưu ạ


  • 0
    tombach1102  commented on Sept. 3, 2025, 5:04 p.m.

    Bài này dùng sàng mà bị quá bộ nhớ thì phải làm sao ạ?


    • 1
      angwangsushi  commented on Oct. 7, 2025, 1:36 p.m. ← edited

      Vậy thì b đừng sàng nữa, thử nghĩ cách khác xem sao?

      Hint

      Bạn có thể sử dụng prefixSum, và hàm bool kiểm tra số nguyên tố như thông thường.


  • 0
    tathaolqd  commented on Feb. 20, 2025, 3:58 p.m.

    tổng tiền tố


  • 1
    vlthhiep08  commented on Feb. 10, 2025, 2:27 a.m.

    Sub 3 để 1e6 nhưng phải 8e6 mới AC ?


    • 1
      lhoangminh126  commented on May 13, 2025, 11:05 a.m.

      Sub3 nhưng bị dính 1e8 từ sub2 á


  • -19
    quannmq2009  commented on Dec. 12, 2024, 4:28 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 0
    TriHuongBG  commented on Aug. 1, 2024, 10:35 a.m.

    oh me


  • 7
    melondepchai  commented on June 23, 2024, 12:38 p.m.

    fact: bài này khỏi sàng vẫn ổn :D


  • -16
    huypro  commented on Feb. 26, 2024, 12:17 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -29
    ChulgCyel  commented on Feb. 24, 2024, 8:23 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 0
      manhvuvanyeuha  commented on Feb. 25, 2024, 2:34 p.m.

      code này sao ac nổi


  • 0
    phamvuhoang486  commented on Jan. 27, 2024, 2:03 p.m. ← edited

    Các bạn có thể chia subtask ra làm cũng AC được nha


  • 2
    thanhhoang  commented on Jan. 23, 2024, 6:51 p.m.

    Sàng nguyên tố.


  • -18
    themluachon2008  commented on Jan. 23, 2024, 7:47 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.