0pts做法

先听一遍揽佬新专，进鼓的时候把嘟嘟嘟大学习交上去就可以拿0pts了。

当然，你也可以像我一样赛时被@在代码里加了一行#include<windows.h>

30pts做法

一个区间 $[l,r]$ ，是合法的当且仅当 $gcd[l,r]=min[l,r]$

写个 $st$ 表然后枚举 $l$ 和 $r$ 就做完了。

100pts但不是最快做法

$st$ 表的 $gcd$ 和 $min$ 查询是 $O(1)$ 的，而且答案长度是关于可行性单调的，二分就做完了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int re(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(f=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
const int N=3e5+10;
const int logN=22;
int stgcd[N][logN];
int stmin[N][logN];
int a[N];
int lg2[N];
int n;
inline int gcd(int x,int y){
	if(x%y==0)return y;
	return gcd(y,x%y);
}
inline void inits(){
	lg2[2]=1;
	for(int i=3;i<N;i++)lg2[i]=lg2[i/2]+1;
}
inline int GCD(int l,int r){
	int m=lg2[r-l+1];
	return gcd(stgcd[l][m],stgcd[r-(1<<m)+1][m]);
}
inline int MIN(int l,int r){
	int m=lg2[r-l+1];
	return min(stmin[l][m],stmin[r-(1<<m)+1][m]);
}
inline bool check(int x){
	for(int i=1;i<=n;i++){
		int l=i,r=i+x-1;
		if(r>n)continue;
		if(GCD(l,r)==MIN(l,r))return 1;
	}
	return 0;
}
int ans;
int tot;
int ll[N];
signed main(){
	inits();
	n=re();
	for(int i=1;i<=n;i++)a[i]=re(),stgcd[i][0]=stmin[i][0]=a[i];
	for(int j=1;j<=logN;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			stgcd[i][j]=gcd(stgcd[i][j-1],stgcd[i+(1<<(j-1))][j-1]);
			stmin[i][j]=min(stmin[i][j-1],stmin[i+(1<<(j-1))][j-1]);
		}
	}
	int l=1,r=n;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid))l=mid+1,ans=mid;
		else r=mid-1;
	}
	for(int i=1;i<=n;i++){
		int l=i,r=i+ans-1;
		if(i+ans-1>n)break;
		if(GCD(l,r)==MIN(l,r))ll[++tot]=l;
	}
	cout<<tot<<" "<<ans<<endl;
	for(int i=1;i<=tot;i++)cout<<ll[i]<<" ";
	return 0;
}