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:
bedao
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.


  • 0
    van353735  commented on Aug. 20, 2024, 9:34 a.m.

    dùng '\n' mới ko bị TLE :))


  • 0
    khanhhoccode  commented on May 26, 2024, 7:33 a.m.

    mn ơi có ai code bằng python không ạ chỉ em ac bài này với ạ em dùng sàng toàn bị TLE ;-;


    • -1
      hosyquan16062007  commented on Aug. 11, 2024, 8:01 a.m.

      cho mimh tham kham code vs a


  • 2
    Groot  commented on April 27, 2024, 4:10 p.m.

    sàng tới 1e7 không được nhỉ?? phải làm đơn thuần hàm kiểm tra snt.

    Và thêm 3 dòng thần chú:

    ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

endl -> '\n'

    thì mới chạy nổi @@


    • 0
      hieuhfgr  commented on May 26, 2024, 3:26 p.m.

      cau than chu thu 2:

      #pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

  • 1
    mainamdc2008  commented on April 22, 2024, 3:41 p.m.

    cho mình hỏi là để tên file như nào vậy ạ?


    • 2
      hoanglongg  commented on April 24, 2024, 2:02 p.m.

      Không để file nha bạn!


  • 1
    khangnguyen1108  commented on Feb. 28, 2024, 8:55 a.m.

    bài sàng + với pref. Nhưng mà tui AC khi dùng printf chứ dùng cout nó TLE ảo vc, tui hong bíc tại sao=))


  • -8
    ChulgCyel  commented on Feb. 24, 2024, 9:14 a.m.

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


    • 12
      x  commented on Feb. 24, 2024, 9:38 a.m.


  • -2
    ChulgCyel  commented on Feb. 24, 2024, 9:13 a.m.

    include<bits/stdc++.h>

    define ll long long

    using namespace std; ll c[100005]={0}; int kt(ll z){ if(z<2)return 0; for(int i=2;i<=sqrt(z);i++) if(z%i==0)return 0; return 1; } int main() { iosbase::syncwith_stdio(false); cin.tie(NULL);cout.tie(NULL); ll n,t,u,v,x; cin>>n>>t; for(int i=1;i<=n;i++){ cin>>x; c[i]=c[i-1]+x; } while(t--){ cin>>u>>v; cout<<kt(c[v]-c[u-1])<<'\n'; } return 0; }


  • -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 ạ


  • -1
    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
      buitathu1706  commented on Feb. 24, 2024, 1:58 p.m.

      do bạn chưa thêm lệnh tăng tốc đấy


    • 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