This way

题意：

给你一个长度为n的数组，你要修改其中的某些值使得任意的l,r, g c d ( a [ l ] , a [ l + 1 ] . . . a [ r ] ) = = r − l + 1 gcd(a[l],a[l+1]...a[r])==r-l+1 gcd(a[l],a[l+1]...a[r])==r−l+1的情况不存在。
对于所有的前缀都做一遍。

题解：

这道题…解题思路在题目中提到了：枚举所有右端点，然后检查左端点。
具体是检查什么，怎么检查。那么我们第一个可以发现的是答案一定是不会减小的，因为你要能让i这个位置满足，必然要让前面的位置也满足。怎么改很重要，如果改不好的话，那是否前面检查过的位置在后面还需要检查一遍呢？
其实很简单，如果当前位置要改，直接改成与当前所有数都互质的数即可。那么后面的位置检查到这里的时候，gcd一定会变成1，也就不用再往前面检查了。
如果我们枚举右端点，然后再枚举左端点检查是否gcd和长度相等的话，时间复杂度是O(n^2)的，怎么办？
可以发现这样一个规律：左端点往左移动的时候，长度一定增加，gcd一定不增加，也就是你右端点往右走的同时，gcd和长度相等的位置一定不会往左移动。
考虑尺取，对于如何快速地求出gcd的问题，使用线段树即可。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],gcd[N*4];
void build(int l,int r,int root){
    if(l==r){
        gcd[root]=a[l];
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,root<<1);build(mid+1,r,root<<1|1);
    gcd[root]=__gcd(gcd[root<<1],gcd[root<<1|1]);
}
int query(int l,int r,int root,int ql,int qr){
    if(l>=ql&&r<=qr)return gcd[root];
    int ans=0,mid=l+r>>1;
    if(mid>=ql)ans=query(l,mid,root<<1,ql,qr);
    if(mid<qr)ans=__gcd(ans,query(mid+1,r,root<<1|1,ql,qr));
    return ans;
}
int main()
{
    int n,pos=0,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    build(1,n,1);
    for(int i=1;i<=n;i++){
        if(a[i]==1)ans++,pos=i;
        else{
            int g=query(1,n,1,pos+1,i);
            while(g<i-pos){
                pos++;
                g=query(1,n,1,pos+1,i);
            }
            if(g==i-pos)
                ans++,pos=i;
        }
        printf("%d%c",ans," \n"[i==n]);
    }
    return 0;
}