HSG THPT Hải Phòng 2023 - Bài 3

View as PDF

Submit solution


Points: 0.01 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem source:
Kỳ thi Học sinh giỏi THPT TP Hải Phòng 2023
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một dãy gồm ~n~ số nguyên ~a_1,a_2,...,a_n~ và ~m~ câu hỏi dạng ~u,v~ ~(1 \le u \le v \le n)~. Với mỗi câu hỏi có dạng trên, hãy kiểm tra xem tổng các số nguyên ~a_u + a_{u+1} + \ldots + a_v~ có phải số nguyên tố hay không?

Input

Dòng đầu tiên chứa hai số nguyên dương ~n,m~ là số phần tử trong dãy và số câu hỏi.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(|a_i| \le 10^4)~.

~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~u,v~ tương ứng là câu hỏi thứ ~i~ yêu cầu kiểm tra tổng các số nguyên ~a_u + a_{u+1} + \ldots + a_v~ có phải số nguyên tố hay không?

Output

In ra ~m~ dòng, dòng thứ ~i~ ~(1 \le i \le m)~ tương ứng với kết quả của câu hỏi ~i~, ghi số ~1~ nếu là tổng các số nguyên tố, ngược lại ghi số ~0~.

Scoring

Subtask % số test Giới hạn
1 ~70\%~ ~n \le 10^3; m \le 10^5~
2 ~30\%~ ~n \le 10^3; m \le 10^6~

Sample Input 1

5 3
2 7 3 4 6
3 4
3 5
2 4

Sample Output 1

1
1
0

Notes

~a_3 + a_4 = 3+4 = 7;~

~a_3 + a_4 + a_5 = 3 + 4 + 6 = 13;~

~a_2 + a_3 + a_4 = 7 + 3 + 4 = 14.~


Comments

Please read the guidelines before commenting.



  • -1
    Thang24_  commented on Feb. 7, 2024, 8:09 a.m.

    mình xài sàng đến 1e7 nộp lên nó bị lỗi phân đoạn là sao ạ


  • 0
    tiykumaa  commented on Jan. 30, 2024, 2:47 p.m.

    bài này sàng ntn cho kịp 1s ạ, e cứ TLE mãi T_T


    • 0
      wipad0310  commented on Jan. 31, 2024, 9:00 a.m.

      sàng kịp mà bạn, sàng tầm 10^7 số mất có 0,078s thôithôi