官方题解挺好的，我这个是官方题解的st版本。

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 200000, LN = 20;

int f[N][LN];
int n;
int a[N];

int gcd(int a, int b)// dddd
{
    if(b == 0) return a;
    else return gcd(b, a % b);    
}

void init() //st预处理所有区间的的gcd
{
    for(int st = 0; (1 << st) <= n; st ++)
        for(int i = 0; i <=  n - (1 << st); i ++)
        {
            if(st == 0)
            {
                f[i][st] = a[i];
                continue;
            }

            f[i][st] = gcd(f[i][st - 1], f[i + (1 << (st - 1))][st - 1]);
        }
}

int getgcd(int l, int r) //st的查询函数
{
    int st = __lg(r - l + 1); //找到最高位位数的__lg函数
    return gcd(f[l][st], f[r - (1 << st) + 1][st]);
}


int main()
{
    cin >> n;

    for(int i = 0; i < n; i ++) cin >> a[i];
    init();
    int maxr = -1;
    int be = 0;
    int res = 0;

    //区间贪心,找到最小的r并让所有包含r的区间(for a fixed l, as r increaes, gcd never changes;you should use less operates to make value as a
    // as great as possible, so by iterating ,you can obtain a r(max), which getgcd(l, r) >= r - l + 1)全部砍掉（a[r] == a big prime）
    for(int i = 0; i < n; i ++)
    {
        while(be < i && getgcd(be, i) < i - be + 1) be ++;
        if(getgcd(be, i) == i - be + 1)
            if(be > maxr)
            {
                res ++;
                maxr = i;
            }

        cout << res << ' ';
    }

    return 0;
}