Chú gấu Tommy và các bạn

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Điểm: 300 Thời gian: 1.0s Bộ nhớ: 500M Input: bàn phím Output: màn hình

Chú gấu Tommy là một chú gấu rất dễ thương. Một ngày nọ chú đến trường và
được thầy dạy về những con số nguyên tố. Chú và các bạn vô cùng thích thú và lao vào
tìm hiểu chúng. Thế nhưng, càng tìm hiểu sâu chú lại càng gặp phải những bài toán
khó về số nguyên tố. Hôm nay thầy giao cho cả lớp một bài toán khó và yêu cầu cả lớp
ai làm nhanh nhất sẽ được thầy cho bánh. Vì thế, để có bánh ăn, Tommy phải giải bài
toán nhanh nhất có thể. Bài toán như sau:

Cho dãy \(n\) số nguyên dương \(x_1, x_2, ..., x_n\) và \(m\) truy vấn, mỗi truy vấn được cho
bởi 2 số nguyên \(l_i, r_i\). Cho một hàm f(p) trả về số lượng các số \(x_k\) là bội của \(ơ\). Câu trả
lời cho truy vấn \(l_i, r_i\) là tổng \(\sum_{p \in S(l_i,r_i)} f(p)\), trong đó \(S(l_i,r_i)\) là tập các số nguyên tố
trong đoạn \([l_i,r_i]\)

Bạn hãy giúp chú gấu Tommy giải bài toán này nhé!

Input

  • Dòng đầu tiên chứa số nguyên \(n (1\le n \le 10^5)\)

  • Dòng thứ 2 chứa n số nguyên dương \(x_1, x_2, ..., x_n (2 \le x_i \le 10^7)\)

  • Dòng thứ 3 chứa số nguyên \(m (1 \le m \le 50000)\). Mỗi dòng \(i\) trong \(m\) dòng sau
    chứa 2 số nguyên ngăn cách bởi 1 dấu cách \(l_i, r_i\) \((2 \le l_i \le r_i \le 2\times 10^9 )\)

Output

  • Gồm \(m\) dòng, mỗi dòng 1 số nguyên là câu trả lời cho một truy vấn.

Example

Test 1

Input 
6
5 5 7 10 14 15
3
2 10
3 12
4 4
Output 
9
7
0
Note

3 truy vấn

  1. Truy vấn 1: l = 2, r = 11.
    Ta cần tính: f(2) + f(3) + f(5) + f(7) + f(11) = 2 + 1 + 4 + 2 + 0 = 9.
  2. Truy vấn 2: l = 3, r = 12.
    Ta cần tính: f(3) + f(5) + f(7) + f(11) = 1 + 4 + 2 + 0 = 7.
  3. Truy vấn 3: l = 4, r = 4 → không có số nguyên tố.

Bình luận


  • 1
    huyhau6a2    9:51 p.m. 10 Tháng 5, 2022

    test bị ảo à, mấy test cuối có cái xuất 0, có cái không, mà trong khi đó rõ ràng là có gì đó sai sai, ai giải thích giúp mình được không ạ

    vd: test 5 trong bài thì có truy vấn đầu tiên là "7797 34646248" mà rõ ràng nếu loại các snt>1e7 ra thì cũng còn đoạn "7797 10000000" nữa, đảm bảo kết quả lớn hơn 0 mà sao lại xuất 0???


    • 0
      dang7rickroll    6:44 a.m. 11 Tháng 5, 2022

      Hmmm


      • -1
        PhanHuyKhang    10:30 a.m. 11 Tháng 5, 2022

        sao a ac được vậy


        • 0
          dang7rickroll    10:34 a.m. 11 Tháng 5, 2022

          Chắc test bị lỗi rồi, để anh về xem lại rồi sinh bộ test mới nhé.

    3 bình luận nữa