HSG THPT Hải Phòng 2023 - Bài 3
View as PDFCho 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
Bai nay ko can sang, chi can dung ham kiem tra nguyen to binh thuong la ok roi. Dung prefix sum ket hop kiem tra nguyen to thi AC ngon lanh luon vi bai nay gioi han kha thap.
include<bits/stdc++.h>
using namespace std; bool ktnt(long long x) { if(x<2)return false; if(x==2)return true; if(x%2==0)return false; for(int i=3;i*i<=x;i+=2) if(x%i==0)return false; return true; } long long a[1005],pref[1005]; int main() { iosbase::syncwith_stdio(false); cin.tie(NULL); long long n,m; cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; pref[0]=0; for(int i=1;i<=n;i++)pref[i]=pref[i-1]+a[i]; while(m--) { long long u,v; cin>>u>>v; long long tong=pref[v]-pref[u-1]; if(ktnt(tong))cout<<1; else cout<<0; cout<<'\n'; } return 0; } mong la bai lam nay se giup moi nguoi! Cho minh xin 1 upvote
include <bits/stdc++.h>
using namespace std; bool isPrime(int n){ if (n<2) return false; else{ for (int i=2;i*i<=n;i++){ if (n%i==0) return false; } return true;
} } const int MAXN=1e4+1; int a[MAXN]; int n,m; int main(){ iosbase::syncwith_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; int pre[n+1]={0}; for (int i=1;i<=n;i++) cin>>a[i]; for (int i=1;i<=n;i++){ pre[i]=pre[i-1]+a[i]; } while (m--){ int x,y; cin>>x>>y; if (isPrime(pre[y]-pre[x-1])){ cout<<1<<"\n"; } else cout<<0<<"\n"; }
include <bits/stdc++.h>
using namespace std; const int MAX=1e7; vector<int> ips; void sieve(){ ips.assign(MAX+1,true); ips[1]=ips[0]=false; for(int i=2;ii<=MAX;i++){ if(ips[i]){ for(int j=ii;j<=MAX;j+=i){ ips[j]=false; } } } } int main(){ iosbase::syncwith_stdio(false); cin.tie(NULL); int n,m; cin>>n>>m; vector<int> a(n+1),b(n+1,0); for (int i = 1; i <= n; i++) { cin >> a[i]; b[i] = b[i - 1] + a[i]; }
} sàng đến 10^7 rồi thêm thần chú
iosbase::syncwith_stdio(false); cin.tie(NULL);
Lý do dùng sàng bị RTE: Do ~|a_i| \le 10^4~ ~\Rightarrow~ ~-10^4 \le a_i \le 10^4~ ~\Rightarrow~ tổng của dãy thuộc đoạn ~[-10^7, 10^7]~. Vì vậy cần phải xử lí trường hợp số âm khi kiểm tra tính nguyên tố bằng sàng, do mảng trong C++ không thể có chỉ số là số âm.
sao mình sàng 1e7 toàn runtime nhỉ =))
ok ac r :))
This comment is hidden due to too much negative feedback. Show it anyway.
0,68s
ai bị RE thì nhớ tổng từ u tới v có thể âm
CODE TRÂU AC 14/20 CÒN MUỐM FULL THÌ PHẢI DÙNG TỔNG TIỀN TỐ ĐÂY LÀ CODE TRÂU:
include <iostream>
include <bits/stdc++.h>
define int long long
using namespace std; bool nt(int n) { if(n<2) return false; for(int i=2;i<=sqrt(n);i++) { if(n%i==0) return false; } return true; } int a[1000001],pre[10000001]; signed main() { int n,q; cin>>n>>q; for(int i=1;i<=n;i++) { cin>>a[i]; } while(q--) { int u,r; cin>>u>>r; int sum=0; for(int i=u;i<=r;i++) { sum+=a[i]; } if(nt(sum)){ cout<<"1"<<endl; }else{ cout<<"0"<<endl; } } return 0; }
lam kieu gi cung bi tle, lam sang hay kiem tra cung tle 5 test cuoi
bài này mình dùng kiểm tra nguyên tố mới full được, còn sàng đến 10^7 vẫn bị sai mất 5 test cuối
bài này mình đã không đọc kỹ đề , phải sàng đến 10 mũ 7 cơ, dùng thêm mảng cộng dồn để truy vấn nhanh hơn thì AC đượđược
Hint:
Sao em sang ma no cu Re vay 😭
This comment is hidden due to too much negative feedback. Show it anyway.
dùng '\n' mới ko bị TLE :))
thiệt luôn trời,đổi sang \n cái ac hết:)))
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 ;-;
python thì bỏ th bạn
This comment is hidden due to too much negative feedback. Show it anyway.
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ú:
thì mới chạy nổi @@
cau than chu thu 2:
thần chú này đang từ tle thành ac :v
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=))
This comment is hidden due to too much negative feedback. Show it anyway.
thánh kiếm đâu ra hình hay quá!!
This comment is hidden due to too much negative feedback. Show it anyway.
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