记录编号	349838	评测结果	AAAAATEEEE
题目名称	军队	最终得分	50
用户昵称	Mealy	是否通过	未通过
代码语言	C++	运行时间	1.933 s
提交时间	2016-11-15 12:05:26	内存使用	118.64 MiB

/*

2547. 军队

tarmy.in

*/

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long ll;


const int nmax=5086;



ll pre[nmax]={0};

int n,K;

int s[nmax]={0}; 

int tmp[nmax]={0};
int l[nmax][nmax]={0};
int ans=0;


int c[nmax][nmax]={0};


int GCD(int a,int b)
{
	return b==0?a:GCD(b,a%b);
}


void PreDo()
{
	scanf("%d%d",&n,&K);
//	printf("%d ",GCD(n,K));
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&s[i]);
		pre[i]=pre[i-1]+(ll)s[i];
	}
	/*
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)
		{
			if(GCD(s[i],s[j])==1)
			{
				c[j]++;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		printf("%d ",c[i]);
	}
	*/
	
	/*
	for(int i=1;i<=n;i++)
	{
		printf("%d ",s[i]);
	}
	*/
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)
		{
			/*if(GCD(s[i],s[j])==1)
			{
				l[i][j]=1;
			}
			*/
			
			l[i][j]=GCD(s[i],s[j]);
//			printf("%d ",GCD(s[i],s[j]));
			l[j][i]=l[i][j];
			
//			printf("%d ",l[i][j]);
		}
//		printf("\n");
	}
	
//	for(int )
	
	
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{	
			int tag=0;
			for(int k=i;k<j;k++)
			{
//				printf("%d")
				if(l[k][j]!=1)
				{
					tag=1;
					break;
				}
			}
			if(tag==0&&pre[j]-pre[i]+s[i]>=K)
			{
				tmp[i]++;
			}
			if(tag==1)
			{
				break;
			}
		}
	}
	/*
	for(int i=1;i<=n;i++)
	{
		printf("%d\n",tmp[i]);
	}
	*/
	
	
	for(int i=1;i<=n;i++)
	{
		ans=max(ans,tmp[i]);
	}
	if(ans==0)
	{
		printf("%d\n",ans);
	}
	else
	{
		printf("%d\n",ans+1);
	}
}



int main()
{
	freopen("tarmy.in","r",stdin);
	freopen("tarmy.out","w",stdout);
	PreDo();
	return 0;
}