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.


  • 2
    trantrunghg99  commented on March 3, 2025, 12:17 p.m.

    ai bị RE thì nhớ tổng từ u tới v có thể âm


  • -2
    tathaolqd  commented on Feb. 10, 2025, 1:49 p.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; }


  • 1
    duymanh080929  commented on Jan. 22, 2025, 8:25 a.m.

    lam kieu gi cung bi tle, lam sang hay kiem tra cung tle 5 test cuoi


  • 0
    daotrungkiena1k46  commented on Jan. 13, 2025, 2:08 p.m.

    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


  • 0
    dmnguyel23  commented on Jan. 6, 2025, 2:50 a.m.

    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


  • 2
    avatronic  commented on Dec. 29, 2024, 1:13 a.m. ← edited

    Hint:

    Chú ý kích thước mảng, có thể dùng static, với kiểm tra kĩ biến tổng tránh trường hợp tràn số. Đã fix và từ RTE --> AC <(")


  • -1
    nguyenanhunter  commented on Nov. 11, 2024, 1:08 a.m.

    Sao em sang ma no cu Re vay 😭


  • -4
    khnguyen21th06  commented on Oct. 20, 2024, 1:40 p.m.

    include <bits/stdc++.h>

    using namespace std;

    define ll long long

    define fi first

    define sec second

    define pb push_back

    define pob pop_back

    define lb lower_bound

    define ub upper_bound

    define FOR(i, a, b) for (int i = a; i < b; ++i)

    define fr(i, a, b) for (int i = a; i <= b; ++i)

    define frd(i, a, b) for (int i = b; i >= a; --i)

    define _nkhanhcp signed main()

    define hackSpeed iosbase::syncwith_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    define TIME (1.0 * clock() / CLOCKSPERSEC)

    typedef vector<int> vii; typedef vector<ll> vll; typedef pair<int, int> pii; typedef pair<ll, ll> pll;

    const int N = (int)3e6 + 9; const int maxN = (int)1e6; const int MOD = (int)1e9 + 7;

    int n, m, a[maxN + 1]; int pre[maxN + 5] = {0}; bool prime[maxN + 1];

    void init(){ cin >> n >> m; fr(i, 1, n) cin >> a[i]; }

    void sieve(){ memset(prime, 1, sizeof(prime)); prime[0] = prime[1] = false; fr(i, 2, sqrt(maxN)){ if (prime[i]){ for (int j = i * i; j <= maxN; j += i) prime[j] = false; } } }

    void solve(){ fr(i, 1, n){ pre[i] = pre[i - 1] + a[i]; } }

    _nkhanhcp{ hackSpeed // freopen("TASK.inp", "r", stdin); // freopen("TASK.out", "w", stdout);

    sieve();
init();
while (m--){
    int u, v; cin >> u >> v;
    solve();
    ll ans = pre[v] - pre[u - 1];
    if (prime[ans]) cout << "1\n";
    else cout << "0\n";
}

cerr << "Time elapsed: " << TIME << "s.\n";
return 0;

    }

    sao code này toàn bị RE v mn..., AC có vài test


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

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


    • 0
      NVTai  commented on March 3, 2025, 2:20 p.m.

      thiệt luôn trời,đổi sang \n cái ac hết:)))


  • -2
    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
    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. ← edited

      cau than chu thu 2:

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

      • 0
        nguyenanhunter  commented on Nov. 11, 2024, 10:00 a.m.

        thần chú này đang từ tle thành ac :v


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

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


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

      Không để file nha bạn!


  • 0
    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=))


  • -12
    ChulgCyel  commented on Feb. 24, 2024, 9:14 a.m. ← edited

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


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


      • -2
        QuanIsReal  commented on Oct. 20, 2024, 8:59 a.m.

        thánh kiếm đâu ra hình hay quá!!


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

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


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