牛客小白月赛99 D题

又是一年毕业季

题目背景

牛客小白月赛99

题目描述

样例 #1

样例输入 #1

3
4
2 4 6 5
5
6 2 5 3 2333333
8
11 4 5 14 19 19 8 10

样例输出 #1

3
7
2

做题思路

首先观察到 即需要保证拍照的时刻 大于等于 2

那么就从2开始往上走，如果有人眨眼间隔为2，那么在 2 这个时刻就会有人眨眼。那么就拍照的时刻继续延长。

下一时刻为3，同理如果有人眨眼间隔为3，那么就拍照的时刻继续延长。

这时候发现下一个眨眼间隔是 5 ，因为 4 是 2 的倍数。

以此类推，发现眨眼间隔一定是素数。

而且这个过程其实就是素数筛选的过程，第一个素数 2 ，然后排除 2 的倍数，再进入下一个素数。

这道题需要做一个处理，因为 $n\le 2e5$，所以我们需要通过欧拉函数寻找2e5个素数的最大值是多少即可。

代码

#include <iostream>
#include <algorithm>
#define int long longusing namespace  std;
const int N = 2e7+10;int n , m ,k , w , q;
int a[N];
bool vis[N];
int primes[N], cnt;
bool st[N];void get_primes(int n)
{for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[cnt ++ ] = i;for (int j = 0; primes[j] <= n / i; j ++ ){st[primes[j] * i] = true;if (i % primes[j] == 0) break;}}
}
void init(){get_primes(3e6);
}
inline int read()
{char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}
void solve(){n=read();for(int i=1;i<=n;i++) { a[i]=read();if(a[i]<=2999957)vis[a[i]] = true; }for(int i=0;i<cnt;i++){if(!vis[primes[i]]){printf("%lld\n",primes[i]);break;}}for(int i=1;i<=n;i++)if(a[i]<=2999957)vis[a[i]] = false;
}
signed main(){init();int _=1;_=read();while(_--)solve();return 0;
}