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

#include <cstdio>
#include <cstring>
#include <algorithm>
#define file(x) "tarmy." #x
typedef long long ll;
using std::max;
const int UPB = 1e6, SZ = 8e4, N = 1e5 + 10;
int n, k, a[N], sz, pt[SZ], ans, nl = 1, ext[SZ], upb;
ll sum;
int ip[UPB + 10];
int main() {
	freopen(file(in), "r", stdin);
	freopen(file(out), "w", stdout);
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]), upb = max(upb, a[i]);
	memset(ip, 1, sizeof(ip));
	for (int i = 2; i <= upb; i++) if(ip[i]) {
		pt[++sz] = i;
		ip[i] = sz;
		for (int j = i + i; j <= upb; j+= i) ip[j] = 0;
	}
	for (int i = 1; i <= n; i++) {
		sum += a[i];
		int x = a[i], ll = nl;
		for (int j = 1; j <= sz && pt[j]*pt[j] <= x; j++) if(x%pt[j] == 0){
			nl = max(nl, ext[j] + 1);
			while(x%pt[j] == 0) x/=pt[j];
		}
		if (x > 1) nl = max(nl, ext[ip[x]] + 1);
		for (int k = ll; k < nl; k++) {
			sum -= a[k];
			int x = a[k];
			for (int j = 1; j <= sz && pt[j]*pt[j] <= x; j++) if(x%pt[j] == 0) {
				ext[j] = 0;
				while(x%pt[j] == 0) x/=pt[j];
			}
			if (x > 1) ext[ip[x]] = 0;
		}
		x = a[i];
		for (int j = 1; j <= sz && pt[j]*pt[j] <= x; j++) if(x%pt[j] == 0) {
			ext[j] = i;
			while(x%pt[j] == 0) x/=pt[j];
		}
		if (x > 1) ext[ip[x]] = i;
		if (sum >= k) {
			//if (i - nl + 1 > ans) printf("%d %d\n", nl , i);
			ans = max(ans, i - nl + 1);
		}
	}
	printf("%d", ans);
}