题面
【问题描述】
给定一个有 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。
【输入】
第一行两个整数 n,k 分别表示队伍数量和人数下限
接下来一行 n 个整数,表示每个队伍的人数
【输出】
一行一个整数,表示队伍的最长长度,如果不存在一个这样的队伍,则输出 0
【输入输出样例】
Input
5 14
4 5 12 3 2
Output
2
【数据范围】
对于 10%的数据 n≤10
对于另外 20%的数据 n≤100
对于另外 20%的数据 n≤2∗1000
对于全部的数据 1≤n≤10^5, 1≤s[i]≤10^6, k≤ int。
题解
n^3log直接过？？
数据水的没话说肯定是tham出的数据
（仔细看可以发现我都没有用到k）
如果数据狠一点，那就要处理一下人数的前缀和，在代码某个地方（自己想）加入一个判断是否满足人数大于k的部分
代码
#include <cstdio>
#define ll long long
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while (c>'9'||c<'0') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
const int maxn=1e5+5;
int n,k;
int s[maxn];
int ans[maxn],anss;
int max(int a,int b){return a>b?a:b;}
inline int gcd(int a,int b) {return b==0?a:gcd(b,a%b);}
void init(){
n=read(),k=read();
for (int i(1);i<=n;++i) s[i]=read();
}
void doit(){
for (int i(1);i<=n;++i){
for (int j(i+1);j<=n;++j){
int flag=1;
if (gcd(s[j],s[i])==1){
for (int q(i+1);q<j;q++)
if (gcd(s[j],s[k])!=1) {j=n;flag=0;break;}
}
else break;
if (flag) ans[i]++;
else break;
}
}
for (int i(1);i<=n;++i) anss=max(anss,ans[i]);
printf("%d
",anss+1);
}
signed main(){
file("tarmy");
init();
doit();
return 0;
}