CF359D Pair of Numbers gcd+暴力

利用区间 gcd 个数不超过 log 种来做就可以了~

code: 

#include <bits/stdc++.h>     
#define N 300005 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;  
int n; 
set<int>s;    
struct solve
{ 
	int A[N],pos[N],len[N],gc[N],b[N],top,tmp; 
	void get() 
	{    
		int i,j;   
		for(i=1;i<=n;++i) 
		{
			for(j=1;j<=top;++j) gc[j]=__gcd(gc[j], A[i]);     
			gc[++top]=A[i], pos[top]=i, b[tmp=1]=1;  
			for(j=2;j<=top;++j) if(gc[j]!=gc[j-1]) b[++tmp]=j;  
			for(top=0,j=1;j<=tmp;++j) gc[++top]=gc[b[j]], pos[top]=pos[b[j]];     
			len[i]=i-pos[top]+1;        
		}
	}   
}ori,rev; 
int main() 
{ 
	// setIO("input"); 
	int i,j,re=0,cnt=0; 
	scanf("%d",&n);   
	for(i=1;i<=n;++i) scanf("%d",&ori.A[i]); 
	for(i=1;i<=n;++i) rev.A[i]=ori.A[n-i+1];            
	ori.get(), rev.get();    
	for(i=1;i<=n;++i) re=max(re, ori.len[i]+rev.len[n-i+1]-2);   
	for(i=1;i<=n;++i) if(ori.len[i]+rev.len[n-i+1]-2==re) s.insert(i-ori.len[i]+1);      
	printf("%d %d
",s.size(), re);  
	for(set<int>::iterator it=s.begin();it!=s.end();it++) printf("%d ",*it);   
	return 0; 
}