Description
给定一个有 n 个队伍的人组成的序列， 第 i 个队伍 i 有 s[i]个人组成， 一个 l 到 r 的子序 列是合法的， 当且仅当(((∀i)(∀j)∧ (i≠ j)∧ (l≤i,j≤r))→(gcd(s[i],s[j])=1))， 即对于该序列中任两个 不相同的队伍， 他们人数的最大公约数为 1， 并且要求该子序列的总人数大于等于 k。
且由于每个队伍能够审批携带的仪器是有限的， 所以需要这个队伍(r - l + 1)尽可能长， 请求出这个队伍的最长长度， 若不存在， 请输出 0。
Input
第一行两个整数 n,k 分别表示队伍数量和人数下限
接下来一行 n 个整数， 表示每个队伍的人数
Output
一行一个整数， 表示队伍的最长长度， 如果不存在一个这样的队伍， 则输出 0
Sample Input
5 14
4 5 12 3 2
Sample Output
2
Hint
数据范围：
对于 10%的数据 (n)≤10
对于另外 20%的数据 (n)≤100
对于另外 20%的数据 (n)≤2000
对于全部的数据 1≤ (n)≤(10^5), 1≤ (s[i])≤(10^6), (k)≤ int。
题解
这道题目比较简单，我们需要一步一步地想：
- 根据它是连续的一段，所以就可以O((n^4))的做。
- 现在我们将O((n^2))的搜索优化成O((n))的，然后就是O((n^3))的解决。
- 现在我们发现如果几个数的最大公约数为1，那么他们必然满足：他们没有除了1以外的公约数。
所以根据以上思路，就可以写出下面的代码：
#include<stdio.h>
#include<stdlib.h>
inline int gi(){
int f=1,sum=0;char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
return f*sum;
}
const int maxn=100010;
int s[maxn],p[1000010];
bool judge(int x){
int y=2,ts=x;
while(y*y<=ts){
while(x%y==0){x/=y;if(p[y])return false;}
if(x==1)break;
y++;
}
if(x!=1)if(p[x])return false;
return true;
}
void out(int x){
int y=2,ts=x;
while(y*y<=ts){
while(x%y==0){x/=y;p[y]--;}
if(x==1)break;
y++;
}
if(x!=1)p[x]--;
}
void fj(int x){
int y=2,ts=x;
while(y*y<=ts){
while(x%y==0){x/=y;p[y]++;}
if(x==1)break;
y++;
}
if(x!=1)p[x]++;
}
int max(int a,int b){
return a>b?a:b;
}
int main(){
int i,j,k,n,m;
n=gi();k=gi();
for(i=1;i<=n;i++)s[i]=gi();
int l=1,r=1,sum=0,ans=0;
while(l<n){
if(l>r)r++;
if(judge(s[r])){
fj(s[r]);sum+=s[r];
r++;
}
else{
out(s[l]);sum-=s[l];
l++;
}
if(sum>=k)ans=max(ans,r-l);
}
printf("%d
",ans);
return 0;
}