分析

对于整个数列，因为每一个数只能被一个区间覆盖，所以考虑求出每个数的延伸范围。复杂度 $O(n)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 100;
int read() {int x;scanf("%d",&x);return x;}
int L[N],R[N],n,a[N],Ans,Max;
int main()
{
    n = read();
    for(int i = 1;i <= n;i++) {
        a[i] = read();L[i] = R[i] = i;
    }
    for(int i = 1,l,r;i <= n;i = r + 1) {
        l = i,r = i;
        while((a[l-1]%a[i] == 0) && l > 1) l = L[l-1],L[i] = L[l];
        while((a[r+1]%a[i] == 0) && r < n) r = R[r+1],R[i] = R[r];
        if(R[i] - L[i] + 1 > Max) {Max = R[i] - L[i] + 1;Ans = 1;}
        else if(R[i] - L[i] + 1 == Max) Ans ++;
    }
    printf("%d\n",Ans);
    return 0;
}