分析
考场上暴力水过好评...
然后我的st表查询似乎是log的，然后log三方跑的比log方快，qwq。
我们发现如果一个区间的最小值就是这个区间的gcd，则这个区间合法。所以我们二分区间长度然后枚举起点检验是否合法即可。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
const int LOG = 20;
int n,a[500100],st1[500100][LOG+3],st2[500100][LOG+3],ans[500100],cnt;
inline int gcd(int x,int y){return y?gcd(y,x%y):x;}
inline bool ck(int sum){
int i,j,k;
if(sum==0)return 1;
for(i=1;i+sum<=n;i++){
for(j=LOG;j>=0;j--)
if((1<<j)<=sum){
if(min(st1[i][j],st1[(i+sum)-(1<<j)+1][j])==gcd(st2[i][j],st2[(i+sum)-(1<<j)+1][j]))
return 1;
break;
}
}
return 0;
}
inline void go(int sum){
int i,j,k;
for(i=1;i+sum<=n;i++){
for(j=LOG;j>=0;j--)
if((1<<j)<=sum){
if(min(st1[i][j],st1[(i+sum)-(1<<j)+1][j])==gcd(st2[i][j],st2[(i+sum)-(1<<j)+1][j]))
ans[++cnt]=i;
break;
}
}
if(sum==0)
for(i=1;i<=n;i++)ans[++cnt]=i;
cout<<cnt<<' '<<sum<<endl;
for(i=1;i<=cnt;i++)printf("%d ",ans[i]);
puts("");
return;
}
int main(){
int i,j,k;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]),st1[i][0]=st2[i][0]=a[i];
for(i=1;i<=LOG;i++)
for(j=1;j<=n;j++)if(j+(1<<i)-1<=n){
st1[j][i]=min(st1[j][i-1],st1[j+(1<<(i-1))][i-1]);
st2[j][i]=gcd(st2[j][i-1],st2[j+(1<<(i-1))][i-1]);
}
int le=0,ri=n;
while(ri-le>1){
int mid=(le+ri)>>1;
if(ck(mid))le=mid;
else ri=mid;
}
go(le);
return 0;
}