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


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Ta sẽ sử dụng mảng cộng dồn để có thể tính nhanh tổng đoạn trong mỗi truy vấn.

Để kiểm tra tính nguyên tố của tổng đó, ta có thể chuẩn bị trước bằng cách sàng số nguyên tố, do ~|a_i| \le 10^4~ và ~n \le 10^3~, nên ta cần sàng tới ~10^7~.

Lưu ý rằng tổng có thể âm.


Comments

Please read the guidelines before commenting.



  • 1
    HERO2K8  commented on Dec. 9, 2024, 10:56 a.m.

    include <bits/stdc++.h>

    using namespace std; int a[10000000]; int kt(int a){ for (int i=2;i<=sqrt(a);i++) if (a%i==0) return 1; return 2; } int main() { //freopen("b.inp","r",stdin); // freopen("b.out","w",stdout); int n,i,j,m; cin>>n>>m; int b[n]; b[0]=0; for (i=1;i<=n;i++) cin>>b[i]; for (i=2;i<=n;i++) b[i]=b[i]+b[i-1]; for (i=1;i<=10000000;i++) a[i]=1; a[1]=a[0]=0; for (i=2;ii<=10000000;i++) if (a[i]==1){ for (j=ii;j<=10000000;j+=i) a[j]=0; } while (m!=0){ int x,y; cin>>x>>y; int t=b[y]-b[x-1]; if (t<=1) cout<<0<<endl else>

            if (a[t]==1) cout<&lt;1<<endl; else cout<&lt;0<<endl;}
    
        m--;
    }
    

    cout<<1;

    }

    </endl>