给一个很慢的双log做法

首先答案具有单调性。先二分出来一个 $mid$，然后判断以每个点为起点长度为 $mid$ 的区间是否合法。考虑如何判断是否合法，存在一个数是所有数的因数，等价于 “区间gcd=区间min”，开两个 ST 表维护即可。

复杂度 $\Theta(n\log ^2n)$，本题最劣解。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-')y=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=(x<<3)+(x<<1)+(c^'0');
		c=getchar();
	}
	return x*y;
}
const int N=300005;
int n,a[N],gc[N][20],mi[N][20];
vector<int>vec,tmp;
inline int getmi(int l,int r) {
	int e=log2(r-l+1);
	return min(mi[l][e],mi[r-(1<<e)+1][e]);
}
inline int getgc(int l,int r) {
	int e=log2(r-l+1);
	return __gcd(gc[l][e],gc[r-(1<<e)+1][e]);
}
inline bool check(int mid) {
	tmp.clear();
	for(int i=1; i+mid-1<=n; ++i) {
		int l=i,r=i+mid-1;
		if(getmi(l,r)==getgc(l,r)) tmp.push_back(i);
	}
	if(!tmp.empty()) {
		vec=tmp;
		return 1;
	}
	return 0;
}
signed main() {
	R(n);
	for(int i=1; i<=n; ++i) {
		R(a[i]),gc[i][0]=mi[i][0]=a[i];
	}
	for(int j=1; (1<<j)<=n; ++j) {
		for(int i=1; i+(1<<j)-1<=n; ++i) {
			gc[i][j]=__gcd(gc[i][j-1],gc[i+(1<<j-1)][j-1]);
			mi[i][j]=min(mi[i][j-1],mi[i+(1<<j-1)][j-1]);
		}
	}
	int l=1,r=n,mid,ans=-1;
	while(l<=r) {
		mid=l+r>>1;
		if(check(mid)) l=mid+1,ans=mid;
		else r=mid-1;
	}
	cout<<vec.size()<<" "<<ans<<"\n";
	for(auto v:vec)cout<<v<<" ";
	return 0;
}