额外可以顺手完成的题目：https://www.luogu.com.cn/problem/P1890

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000;
int n;
int h[MAXN + 5];
// st[i][j] 存从 h[i] 开始 2^j 个元素的 gcd
int st[MAXN + 5][25];
int gcdAll(int l, int r)
{
    int j = log2(r - l + 1);
    return __gcd(st[l][j], st[r - (1 << j) + 1][j]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> h[i];

    for (int i = 1; i <= n; i++)
        st[i][0] = h[i];
    for (int j = 1; j <= 20; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            st[i][j] = __gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);

    for (int i = 1; i <= n; i++)
    {
        int l = 1;
        int r = i;
        int maxL = i;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (gcdAll(mid, i) == h[i])
            {
                maxL = mid;
                r = mid - 1;
            }
            else
                l = mid + 1;
        }
        l = i;
        r = n;
        int maxR = i;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (gcdAll(i, mid) == h[i])
            {
                maxR = mid;
                l = mid + 1;
            }
            else
                r = mid - 1;
        }
        cout << maxR - maxL + 1 << " ";
    }
    return 0;
}