HSG THPT Hải Phòng 2023 - Bài 3
Xem dạng PDF
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.~
Bình luận
cho mình hỏi là để tên file như nào vậy ạ?
Không để file nha bạn!
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=))
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
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; }
mình xài sàng đến 1e7 nộp lên nó bị lỗi phân đoạn là sao ạ
bài này sàng ntn cho kịp 1s ạ, e cứ TLE mãi T_T
do bạn chưa thêm lệnh tăng tốc đấy
sàng kịp mà bạn, sàng tầm 10^7 số mất có 0,078s thôithôi