发一篇倍增的题解。

思路

不难发现，对于一个数的询问，我们只需从他向左延申，找到最远的位置，同时保证$\gcd$为$a_i$，再向右延申，最终答案即为$r-l+1$（贪心想法）。

但是如果直接一个一个找肯定会TLE，考虑使用倍增优化。

定义$st_{i,j}$表示从$i$开始，到$i+2^j-1$这一段区间的$\gcd$，具体预处理方法同ST表。

每次查询的时候就从大到小地看是否可以跳，具体实现类似于ST表求LCA，最终两边都找最大区间即可。

时间复杂度$O(n\log^2 n)$，显然不是最优解。

AC代码

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
	if(a>b)swap(a,b);
	if(a==0)return b;
	return gcd(b%a,a);
}
const int N=1e6+10;
int a[N],n;
int st[N][21],lg[N];
int main()
{
	scanf("%d",&n);
	lg[0]=-1;lg[1]=0;for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),st[i][0]=a[i];
	for(int i=1;i<=20;i++)for(int j=1;j+(1<<i)-1<=n;j++)st[j][i]=gcd(st[j][i-1],st[j+(1<<i-1)][i-1]);
	for(int i=1;i<=n;i++)
	{
		int l=i,r=i;
		for(int j=lg[l-1];j>=0;j--)if(l-(1<<j)>0&&st[l-(1<<j)][j]%a[i]==0)l=l-(1<<j);
		for(int j=lg[n-r];j>=0;j--)if(r+(1<<j)<=n&&st[r+1][j]%a[i]==0)r=r+(1<<j);
//		printf("%d %d\n",l,r);
		printf("%d ",r-l+1);
	}
	return 0;
}

$\gcd(a,b)=a(a,b>0)$ 当且仅当 $b$ 是 $a$ 的正整数倍。

写 $n^2$ 暴力时想出来的。

注意到，想写 $n^2$ 暴力直接枚举每个区间再暴力去修改区间内数的答案是不可行的，于是我们就引出接下来一个至关重要的想法：

考虑拆区间，$i$ 所在的最长区间一定是向左扩张最长的区间与向右最长的区间结合在一起，于是就可以枚举区间长度在枚举左/右端点来更新当前点的答案，$n^2$ 的暴力就写完了。

显然，上述代码的瓶颈就在于求最右边（$r_i$）与最左边（$l_i$）在哪，看到题目中的条件，不难发现，$h_i$ 关于 $[l,r]$ 是好的至少要满足 $h_i$ 是 $[l,r]$ 区间内的最小值，于是对于每一个 $i$，能向右扩张的最长至多在右侧的第一个比它小的数。上述问题显然可以用单调栈解决，所以我们考虑对原问题使用单调栈。

那么这就简单了，既然你要找最右侧的第一个不是它的倍数的数，那我们直接维护一个栈，每遇到一个新数，就不断弹栈直到该数为栈顶数的倍数为止，对弹出的数记录答案，于是做完了。

正确性考虑使用数学归纳法证明：我们要证明，在处理完前 $i$ 个数之后，对于栈内的数，栈顶 $i$ 一定是 $[1,i]$ 区间内该数能扩张到的最右端点。

对于 $i=1$ 时，栈内只有 $h_1$，正确性显然。

接下来，假设 $i=1,2\dots,k$ 时是正确的，对于 $i=k+1$ 时，根据算法流程，弹栈后栈顶 $h_{st_{top}}$ 元素一定是 $h_{k+1}$ 的倍数，因为栈顶到栈底的元素下表是递减的，又有 $st_{top}<k+1$，所以对于栈顶下方的元素，$h_{st_{top}}$ 一定是它们对应的 $h$ 的倍数，所以 $h_{k+1}$ 也是它们的倍数。又因为对于栈内的任意一个元素 $x$，一定有 $[x,k]$ 是 $i=k$ 时 $x$ 能向右扩张的最右端点，此时将 $h_{k+1}$ 加入这个区间后一定还是合法的，且 $[x,k+1]$ 就是 $i=k+1$ 时 $x$ 能向右扩张的最右端点，所以在下一步将 $k+1$ 压入栈后对于栈内的元素仍然满足栈顶 $i$ 是 $[1,i]$ 区间内该数能扩张到的最右端点。

所以该算法是正确的，时间复杂度 $O(n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
int beg[1000005];
int ed[1000005];
int a[1000005];
int st[100005];
int to=0;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	} 
	for(int i=1;i<=n;i++){
		while(to && a[i]%a[st[to]]!=0){
			ed[st[to]]=i-1;
			to--;
		}
		st[++to]=i;
	}
	while(to){
		ed[st[to--]]=n;
	}
	for(int i=n;i>=1;i--){
		while(to && a[i]%a[st[to]]!=0){
			beg[st[to]]=i+1;
			to--;
		}
		st[++to]=i;
	}
	while(to){
		beg[st[to--]]=1;
	}
	for(int i=1;i<=n;i++){
		cout<<ed[i]-beg[i]+1<<" ";
	}
	return 0;
}

求 wyh 给我透的做法，我自己的话估计 st 表 + 二分乱搞。

注意到可以分为 $[l, x]$ 和 $[x, r]$ 分别处理，两边处理方式是一样的，这里假设是处理左端点。

对于每个点，我们要找离它最近的不能被它整除的点，即不是该点倍数的最近点，所谓“截断点”。

对于点 $i$ 和再它右边的点 $j$，如果点 $i$ 是点 $j$ 的倍数，无疑点 $j$ 是更好的“ 截断 点”人选。

因为点 $j$ 包含的因子少于（可能等于）点 $i$ 所包含的因子，这样能成为别的点倍数的可能性更小。

这类似滑动窗口取最小值，我们考虑使用单调栈（毕竟又没规定范围）。

#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int N = 1e6 + 10;
LL a[N];
int sta[N], l[N], r[N];
 
int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	
	int tp = 1;
	sta[0] = 0;
	sta[tp] = 1;
	l[1] = 1;
	for (int i = 2; i <= n; i ++) {
		while ((a[sta[tp]] % a[i] == 0) && tp >= 1) {
			tp --;
		}
		l[i] = sta[tp] + 1;
		tp ++; sta[tp] = i;
	}
	
	tp = 1;
	sta[0] = n + 1;
	sta[tp] = n;
	r[n] = n;
	for (int i = n - 1; i >= 1; i --) {
		while ((a[sta[tp]] % a[i] == 0) && tp >= 1) {
			tp --;
		}
		r[i] = sta[tp] - 1;
		tp ++; sta[tp] = i;
	}
	
	for (int i = 1; i <= n; i ++) {
		cout << (r[i] - l[i] + 1) << " ";
	}
	cout << "\n"; 
	 
	
	return 0;
} 

二分。

思路

注意到要求 $l \leq i \leq r$ ，考虑以 $i$ 为起点双指针扩展求最大区间，但是 $O(n^2)$ 在 $n \leq 10^6$ 下显然超时。（实际也是超了） 于是考虑使用二分求左右端点，并用 ST 表维护区间 $\gcd$。

Code:

#include <bits/stdc++.h>

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

int main() {
    int N;
    scanf("%d", &N);

    std::vector<std::array<int, 20>> F(N + 1);
    std::vector<int> log(N + 1);

    log[2] = 1;
    for(int i = 3; i <= N; ++i)
        log[i] = log[i >> 1] + 1;
    
    for(int i = 1; i <= N; ++i)
        scanf("%d", &F[i][0]);

    const int logN = 19;

    for(int k = 1; k <= logN; ++k)
        for(int i = 1; i + (1 << k) - 1 <= N; ++i)
            F[i][k] = gcd(F[i][k-1], F[i + (1 << k-1)][k-1]);
    
    auto query = [&](int l, int r) -> int {
        int lgl = log[r - l + 1];
        int res = gcd(F[l][lgl], F[r - (1 << lgl) + 1][lgl]);

        // fprintf(stderr, "QUERY FROM %d TO %d , GOT %d. \n", l, r, res);
        return res;
    };

    for(int i = 1, l, r; i <= N; ++i) {
        l = r = i;
        
        for(int L = 0, R = i + 1, mid; L + 1 < R; ) {
            mid = L + R >> 1;
            if(query(mid, i) == F[i][0])
                l = R = mid;
            else
                L = mid;
        }

        for(int L = i - 1, R = N + 1, mid; L + 1 < R; ) {
            mid = L + R >> 1;
            if(query(i, mid) == F[i][0])
                r = L = mid;
            else
                R = mid;
        }
        
        printf("%d ", r - l + 1);
    }

}

单调栈简单线性做法。

题意

给定序列 $h_i$，对于每个 $i$，求出包含 $i$ 且 $\gcd\limits_{j=l}^{r}h_j=h_i$ 的最大区间。

思路

$\gcd$ 的本质是对质因数取 $\min$。因此可以转化为查询对于每个质因数，次数最小值等于 $k_i$ 的最大区间，这样的结构可以使用单调栈。维护一个单调栈，满足栈内上一个数不整除下一个数，相当于上一个存在质因数的次数大于这个数的位置。跑两遍单调栈求出每个位置对应的左右端点即可。

代码

#include <bits/stdc++.h>
using namespace std;
constexpr int N=1e6+6;
int n,a[N],l[N],r[N],st[N],top;
signed main(){
    clock_t _st=clock();
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    st[top=1]=l[1]=1;
    for(int i=2;i<=n;i++){
        while(top&&!(a[st[top]]%a[i]))--top;
        l[i]=st[top]+1,st[++top]=i;
    }
    st[0]=n+1,st[top=1]=r[n]=n;
    for(int i=n-1;i>=1;i--){
        while(top&&!(a[st[top]]%a[i]))--top;
        r[i]=st[top]-1,st[++top]=i;
    }
    for(int i=1;i<=n;i++)cout<<r[i]-l[i]+1<<' ';cout<<'\n';
    clock_t _ed=clock();
    cerr<<(_ed-_st)*1.0/CLOCKS_PER_SEC<<'\n';
    return 0;
}