记录编号	349833	评测结果	AAAAAAAAAA
题目名称	军队	最终得分	100
用户昵称	dududu	是否通过	通过
代码语言	C++	运行时间	3.513 s
提交时间	2016-11-15 12:03:57	内存使用	1.07 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
 
const int KN =1e5+10;
int N,K,L=1,R=N;
int data[KN];
int presum[KN];
void init(){
	scanf("%d %d",&N,&K);
	for(int i=1;i<=N;i++) scanf("%d",&data[i]),presum[i]=presum[i-1]+data[i];
	L=1,R=N;
}
int gcd(int a,int b){
	return a ? gcd(b%a,a):b;
}
 
int judge(int l,int r){
	for(int cur=l+1;cur<=r;cur++){
		for(int i=cur-1;i>=l;i--){
			if(gcd(data[cur],data[i])!=1) return i+1;
		}
	}
	return 0;
}
 
bool check(int len){
	int i=1,j=len;
	while(j<=N){
		if(presum[j]-presum[i-1]<K){
			i++,j=i+len-1;
			continue;
		}
		int k=judge(i,j);
		if(!k) return 1;
		else i=k,j=i+len-1;
	}
	return 0;
}
 
void sol(){
	int mid,ans;	
	while(L<R){
		mid=(L+R)>>1;
		if(check(mid)) ans=mid,L=mid+1;
		else R=mid;
	}
	printf("%d",ans);
}
 
int main(){
	freopen("tarmy.in","r",stdin);
	freopen("tarmy.out","w",stdout);
	init();
	sol();
	return 0;
}