记录编号	349954	评测结果	AAAAAAAAAA
题目名称	军队	最终得分	100
用户昵称	jmisnal	是否通过	通过
代码语言	C++	运行时间	1.868 s
提交时间	2016-11-15 14:29:23	内存使用	35.60 MiB

    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <vector>
    #define maxn 1000005
    #define ll long long
    using namespace std;
    int read()
    {
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x;
    }
    bool not_prime[1000005];
    int prime[1000005];
    void Get_prime()
    {
    for(int i=2;i<maxn;i++)
    {
    if(not_prime[i]==0)prime[++prime[0]]=i;
    for(int j=1;j<=prime[0]&&i*prime[j]<maxn;j++)
    {
    not_prime[prime[j]*i]=1;
    if( i%prime[j]==0 )break;
    }
    }
    }
    /*int gcd(int a,int b)
    {
    if(b==0)return a;
    return gcd(b,a%b);
    }*/
    int n,k;
    int a[maxn];
    int syg[maxn],next[maxn];
    void change(int zs,int now)
    {
    for(int i=now+1;i<next[now];i++)
    {	
    if(a[i]%zs==0)
    {
    next[now]=i-1;syg[i]=now+1;
    }
    }
    }
    vector<int>vc[maxn];
    void fj(int cx)
    {
    int now=a[cx];
    for(int i=1;i<=prime[0];i++)
    {
    if(now%prime[i]==0)
    {
    vc[ i ].push_back( cx );
    if(vc[i].size()>=2)
    {
    int s=vc[i][vc[i].size()-2] +1;
    if( syg[ cx ] < s )syg[cx]=s;
    if( next[ s-1 ] > cx-1 )next[s-1]=cx-1;	
    }
    // cout<<cx<<' '<<now<<' '<<prime[i]<<endl;
    now/=prime[i];
    }
    while(now%prime[i]==0)now/=prime[i];
    if(now==1)return;
    }
    }
    ll S[maxn];
    int main()
    {
    	freopen("tarmy.in","r",stdin);
    	freopen("tarmy.out","w",stdout);
   // freopen("abcd.in","r",stdin);
    Get_prime();
    n=read();k=read();
    for(int i=1;i<=n;i++)
    {
    a[i]=read();
    S[i]=S[i-1]+a[i];
    syg[i]=0;next[i]=n+1;
    }
    for(int i=1;i<=n;i++)
    fj(i);
    // for(int i=1;i<=n;i++)
    // cout<<i<<' '<<syg[i]<<' '<<next[i]<<endl;
    int ans=0;
    // cout<<"========="<<endl;
    for(int i=1;i<=n;i++)
    {
    int zj=next[i],j;
    for(j=i+1;j<=zj;j++)
    {
    if(next[j]<zj)zj=next[j];	
    }
    // cout<<i<<' '<<j<<' '<<zj<<' '<<S[zj]-S[i-1]<<' '<<ans<<endl;
    if( S[zj]-S[i-1] >= k)
    ans=max(ans, j-i );
    }	
    printf("%d",ans);
    return 0;
    }