D. Playlist

对于一个序列 我们每一轮至少减少一个
并且减少的多少个同时也只会更新多少个不同的相邻的组
我们运用dsu将相邻gcd大于1的合并
就相当于将这个序列分成几个块 每次我们只询问这么块相邻的是否gcd==1
是我们加入ans 否则我们合并 当且仅当我们的ans数组为n了或者是只剩下一个块了
那么break即可

int p[N];
int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
void merge(int x, int y){
    p[find(x)] = find(y);
}
void solve(){
    int n;cin>>n;
    vector<int>a(n),ans,nxt(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
        p[i]=i;
        nxt[i]=(i+1)%n;
    }
    int c=0;
    while(1){
        int pc=find(c);
        if(__gcd(a[pc],a[nxt[pc]])>1){
            if(find(pc)==find(nxt[pc]))break;
            merge(pc,nxt[pc]);
            c=nxt[pc];
        }else{
            if(ans.size()==n)break;
            ans.push_back(nxt[pc]+1);
            c=nxt[pc]=nxt[nxt[pc]];
        }
    }
    cout<<ans.size()<<' ';
    for(auto i:ans)cout<<i<<' ';cout<<endl;
}