思路：当 $a_i$ 为 $1$ 时跨过 $i$ 的区间 $\gcd$ 只可能为 $1$，于是分为 $[1,i)$ 和 $(i,n]$ 做。前一半考虑先从前往后扫一遍然后撤回，后一半从后往前边扫边做。

求的具体方法（以从前往后为例）：对于第 $i$ 个点，考虑拿着它往前求区间 $\gcd$。设当前区间 $\gcd$ 值为 $x$，正在和 $a_j$ 求，如果 $x=1$ 那么显然没有继续求的必要；如果 $\gcd(x,a_j)=a_j$ 那么说明再走下去答案会和从 $a_j$ 开始走下去的答案一样，也可以不继续求下去；否则就令 $x\gets \gcd(x,a_j)$ 继续往前走。每次 $\gcd$ 如果变化一定至少减半，于是至多往前走 $O(\log n)$ 轮，求 $\gcd$ 是 $O(\log n)$ 的故总复杂度 $O(\log^2n)$。弄个桶记录当前 $\gcd$ 的值的数量，另开一个变量记录非 $0$ 数量表示种类数。第一步从前往后扫时，每个点都存储一下它有哪些新的 $\gcd$ 贡献，撤回时扫一遍在桶里逐个删除即可。我发现每个点一个 vector 会炸，所以开了个栈，然后记录每个点往里放了几个数；撤回是从后往前的，对应的上栈。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
int a[maxn], n;
namespace Table {
    int tot = 0; long long table[maxn];
    void add(int x) { tot += (table[x] == 0), table[x] ++; }
    void del(int x) { table[x] --, tot -= (table[x] == 0); }
} using namespace Table;
int gcd(int u, int v) { return v == 0 ? u : gcd(v, u % v); }
int value[maxn * 21], top, more_cnt[maxn]; int ans[maxn];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++)
        scanf("%d", &a[i]);
    add(a[1]); more_cnt[1] = 1, value[++ top] = a[1];
    for (int i = 2; i < n; i ++) {
        int x = a[i]; add(x); more_cnt[i] = 1, value[++ top] = x;
        for (int j = i - 1; j >= 1; j --) {
            if (x == 1) break; int g = gcd(a[j], x);
            if (g != a[j]) value[++ top] = g, more_cnt[i] ++, add(x = g); 
            else break;
        }
    }
    for (int i = n; i >= 1; i --) {
        for (; more_cnt[i]; more_cnt[i] --) del(value[top --]);
        add(1);
        if (i < n) {
            int x = a[i + 1]; add(x); 
            for (int j = i + 2; j <= n; j ++) {
                if (x == 1) break; int g = gcd(a[j], x);
                if (g != a[j]) add(x = g); 
                else break;
            } 
        } ans[a[i]] = tot, del(1);
    } for (int i = 1; i <= n; i ++) printf("%d ", ans[i]);
    return 0;
}

感谢您的耐心阅读！