HSG9 Ninh Bình 2025 - Xâu nguyên tố cùng nhau

Điểm: 40,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 1G

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C++, Java, Output Only, Pascal, PyPy, Python, ~~Scratch~~, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Bình luận

Hãy đọc nội quy trước khi bình luận.

petercon123 đã bình luận lúc 4, Tháng 10, 2026, 14:22

include <bits/stdc++.h> using namespace std;

#define ll long long const ll N=1e6+1; ll n,a[N],b,x,y,k,dem[N],spf[N+1]; string s; int main(){ cin>>s; ll  n=1,vt=0; s+=' ';  for(int i=0;i&lt;s.size();i++){
    if(s[i]<='9' && s[i]>='0')
    vt=vt*10+s[i]-48; else { if(vt>0){
            a[n++]=vt;
            vt=0;
        }

} }

for(int i=2;i&lt;N;i++)
    spf[i]=i;

for(int i=2;i*i&lt;N;i++){
    if(spf[i]==i){
        for(int j=i*i;j&lt;N;j+=i){
            if(spf[j]==j)
            spf[j]=i;
        }
    } }

ll l=1,ans=0;

for(int i=1;i&lt;n;i++){

    k=a[i];

    while(k>1){

        ll p=spf[k];

        l=max(l,dem[p]+1);
        dem[p]=i;

        while(k%p==0)
            k/=p;

    }

    ans=max(ans,i-l+1);

}

cout<&lt;ans; return 0; }