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

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <queue>
#include <cmath>

using namespace std;
typedef long long ll;

int getint() {
    int num = 0; char ch;
    while( isspace(ch=getchar()) );
    do {
        num *= 10; num += ch-'0';
    }while( !isspace(ch=getchar()) );
    return num;
}

bool isprime[1000010];
int prmtb[1000010],tbsz = 0;
void make_prmtb() {
    memset( isprime, true, sizeof(isprime) );
    isprime[1] = isprime[0] = false;
    int e = sqrt(1000010)+1;
    for( int i = 2; i <= e; ++i ) if( isprime[i] ){
        for( int j = i*i; j <= 1000010; j+=i )
            isprime[j] = false;
    }
    for( int i = 2; i < 1000010; ++i ) if( isprime[i] ){
        prmtb[tbsz++] = i;
    }
}

int n,s[100010],k;

int last[1000010]; // 质因数上次的出现位置
int oppo[100010]; // oppo[i]表示前面的最近一个和s[i]冲突的数字的位置
int fctr[1000010],fctrsz; // 临时保存质因数
void getfactor( int num ) {
    fctrsz = 0;
    for( int i = 0; i < tbsz && num > 1; ++i ) {
        if( num % prmtb[i] == 0 ) {
            fctr[fctrsz++] = i;
            while( num > 1 && num % prmtb[i] == 0 )
                num /= prmtb[i];
        }
    }
}

ll pf[100010];
ll getpf( int l, int r ) {
    return l==0 ? pf[r] : pf[r]-pf[l-1];
}

int main() {
    freopen( "tarmy.in", "r", stdin );
    freopen( "tarmy.out", "w", stdout );
    make_prmtb();
    n = getint(); k = getint();
    memset( last, -1, sizeof(last) ); // -1表示不存在上次出现的位置
    memset( oppo, -1, sizeof(oppo) ); // oppo[i] = -1表示i之前不存在数字和s[i]冲突
    for( int i = 0; i < n; ++i ) {
        s[i] = getint();
        pf[i] = i==0 ? s[i] : pf[i-1]+s[i];
        if( s[i] == 1 ) oppo[i] = i-1;
        else {
            getfactor(s[i]);
            for( int j = 0; j < fctrsz; ++j ) {
                oppo[i] = max( oppo[i], last[fctr[j]] );
                last[fctr[j]] = i;
            }
        }
    }
    int ans = s[0]>=k ? 1 : 0;
    int L = 0, R = 1;
    while( R < n ) {
        if( oppo[R] >= L ) L = oppo[R]+1;
        if( getpf(L,R) >= k ) ans = max( ans, R-L+1 );
        ++R;
    }
    printf( "%d\n", ans );
    return 0;
}