记录编号	350738	评测结果	AAAAAAAAAA
题目名称	军队	最终得分	100
用户昵称	kxxy	是否通过	通过
代码语言	C++	运行时间	0.117 s
提交时间	2016-11-15 21:32:49	内存使用	2.12 MiB

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e5+5;
const int maxs=1e6+5;
int n,k,s[maxn],_max,primeb[maxn],p=0;
bool pd[maxn]={0};
inline int read()
{
	int x=0;
	char c=getchar();
	while(c>'9'||c<'0')
		c=getchar();
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
inline void isget_prime()
{
	for(int i=2;i<=_max;i++)
	{
		if(!pd[i])
			primeb[p++]=i;
		for(int j=0;j<p&&primeb[j]*i<=_max;j++)
		{
			pd[primeb[j]*i]=1;
			if(!(i%primeb[j]))
				break;
		}
	}
}
inline void init()
{
	n=read(),k=read();
	for(int i=0;i<n;i++)
		s[i]=read(),_max=max(_max,s[i]);
	isget_prime();
}
int ans=0;
int bls[20];
int rls[20];
bool hv[maxs];
inline void Decomposition_of_the_quality_factor(int x,int *A)
{
	A[0]=1;
	for(int i=0;primeb[i]*primeb[i]<=x;i++)
	{
		if(!(x%primeb[i]))
		{
			A[A[0]++]=primeb[i];
			x/=primeb[i];
			while(!(x%primeb[i]))
				x/=primeb[i];
		}
	}
	if(x>1)
		A[A[0]++]=x;
}
inline void work()
{
	int l=0;
	int S=0;
	for(int i=0;i<n;i++)
	{
		Decomposition_of_the_quality_factor(s[i],bls);
		for(int j=1;j<bls[0];j++)
		{
			while(hv[bls[j]])
			{
    			Decomposition_of_the_quality_factor(s[l],rls);
    			for(int k=1;k<rls[0];k++)
    				hv[rls[k]]=0;
    			S-=s[l++];
			}
			hv[bls[j]]=1;
		}
		S+=s[i];
		if(S>=k)
			ans=max(ans,i-l+1);
	}
	printf("%d\n",ans);
}
int main()
{
	freopen("tarmy.in","r",stdin);
	freopen("tarmy.out","w",stdout);
	init();
	work(); 
	return 0;
}