给一个很快的 $O(n)$ 做法

最开始比较容易想到：对于每个数，找到数左边和右边第一个它不能整除的数，就能确定区间的范围

于是有人就会容易地想到：可以用 $二分$ 。可是这样还不够优秀

于是不容易地想到：可以用 $类似单调栈$ 实现

这个单调栈里面的数需满足：相邻两个数之间呈倍数关系。入栈的时候若不满足，就弹出栈顶，直到满足。

因此，一个数被谁弹出栈，它右侧第一个它不能整除的数就是谁

正着反着跑两遍即可。

150ms，跑得飞快

#include<iostream>
#include<cstdio>

using namespace std;

inline int Rd(){
	int x=0,f=1, c=getchar();
	while (c<'0' || c>'9'){
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
	return x*f;
} 

int n,a[300005];
int st[300005],top, rm[300005],lm[300005];
int maxx,ans[300005],tot;

int main(){
//	freopen("interval.in","r",stdin);
	n=Rd();
	for (int i=1;i<=n;i++){
		a[i]=Rd();
	}
	for (int i=1;i<=n;i++){
		while (top && (a[st[top]]>a[i] || a[i]%a[st[top]]!=0)) rm[st[top--]]=i;
		st[++top]=i;
	}while (top) rm[st[top--]]=n+1;
	
	for (int i=n;i>=1;i--){
		while (top && (a[st[top]]>a[i] || (a[i]%a[st[top]])!=0)) lm[st[top--]]=i;
		st[++top]=i;
	}while (top) lm[st[top--]]=0;
//	for (int i=1;i<=n;i++){
//		cerr<<lm[i]<<" "<<rm[i]<<endl;
//	}cerr<<endl;
	
	for (int i	=1;i<=n;i++){
		int tmp=rm[i]-lm[i]-1;
		if (maxx<tmp){
			maxx=tmp;
			ans[tot=1]=lm[i]+1;
		}else if (maxx==tmp){
			if (ans[tot]!=lm[i]+1){
				ans[++tot]=lm[i]+1;
			}
		}
	}
	printf("%d %d\n",tot,maxx);
	for (int i=1;i<=tot;i++){
		printf("%d ",ans[i]);
	}
	printf("\n");
	return 0;
}

暴力

以每个点为整除的那个数，向两边延伸，复杂度n方

正解

考虑优化暴力。注意到：一个数向左向右延伸到的数，一定是大于等于它的。所以被延伸到的数一定不会再作为整除的那个数（起码不会更新答案）。所以从一个数开始延伸，下次从延伸到的r+1开始暴力就可以。

code

bool M1;
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define look_memory cerr<<abs(&M1-&M2)/1024.0/1024<<"MB\n"

namespace syr
{
	const ll N = 3e5+10;
	ll n, ans;
	ll a[N];
	set <ll> w;
	ll check (ll i) {
		ll l=i, r=i;
		while (l>=1 && a[l]%a[i]==0) l--;
		while (r<=n && a[r]%a[i]==0) r++;
		l++, r--;
		ll len = r-l+1;
		if (ans==len) w.insert(l);
		else if (ans<len) {
			ans = len;
			w.clear();
			w.insert(l);
		}
		return r+1;
	}
	void work()
	{
		cin>>n;
		for (ll i=1; i<=n; i++) cin>>a[i];
		ll x = 1;
		while (x<=n) x = check(x);
		cout<<w.size()<<" "<<ans<<'\n';
		for (ll i : w) cout<<i<<" ";
	}
}

bool M2;

int main()
{
//	freopen("a.in", "r", stdin);
	cin.tie(0)->sync_with_stdio(0);
	look_memory;
	syr::work();
	return 0;
}

给一个很慢的双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;
}

首先我们发现我们要对于每一个数找到其左边右边第一个不能整除的数

找每个数左边右边第一个比其大和比其小的时候都使用单调栈，所以这道题考虑使用单调栈

这个单调栈里面的数需满足：相邻两个数之间呈倍数关系。入栈的时候若不满足，就弹出栈顶，直到满足。

因此，一个数被谁弹出栈，它右侧第一个它不能整除的数就是谁

正着反着跑两遍即可。

目前最优解

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<stack>
#define N 300005
using namespace std;
bool Test_MLE_start;
int _=1,n,cnt=0,ans=0,top=0,a[N],L[N],R[N],p[N],stk[N];
//stack<int> stk;
inline int reads(){
//	char buf[1<<20],*p1,*p2;
//	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
	int c=getchar(),x=0,f=1;
	while(!isdigit(c)) c=getchar_unlocked(); 
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar_unlocked();}
	return x*f;
}inline void files(){
	freopen("A.in","r",stdin);
//	freopen("std.ans","w",stdout);
}inline void clr(){
//	Don't forget!

}int gcd(int a,int b){return b?gcd(b,a%b):a;}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads();
		for(int i(1);i<=n;i++) a[i]=reads();
		for(int i(1);i<=n;i++){
			while(top&&(a[stk[top]]>a[i]||a[i]%a[stk[top]]!=0)) R[stk[top--]]=i;
			stk[++top]=i;
		}while(top) R[stk[top--]]=n+1;
		for(int i(n);i>=1;i--){
			while(top&&(a[stk[top]]>a[i]||a[i]%a[stk[top]]!=0)) L[stk[top--]]=i;
			stk[++top]=i;
		}while(top) L[stk[top--]]=0;
		for(int i(1);i<=n;i++){
			if(R[i]-L[i]-1>ans){
				ans=R[i]-L[i]-1;
				p[cnt=1]=L[i]+1;
			}else if(R[i]-L[i]-1==ans&&p[cnt]!=L[i]+1) p[++cnt]=L[i]+1;
		}printf("%d %d\n",cnt,ans);
		for(int i=1;i<=cnt;i++) printf("%d ",p[i]);
	}exit(0);
}
/*
14
61 30 28 31 23 28 54 56 24 12 28 54 47 67 
*/

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;
}