CF1834E MEX of LCM
题目大意
要你找到一个最小的正整数 x,使得 x 不是序列 a 中任意一个子段的 LCM。
题解
首先考虑一下最坏的情况,即考虑一下答案的上界,容易发现,前 1∼n+1 个质数一定有一个不出现(一个质数能够作为 LCM 当且仅当有这个质数和若干个 1),而这个不出现的质数就可以作为答案。
用一下线性筛,发现第 3e5+1 个质数为 4256233,也就是答案的上界。
Trick
对于一个左端点 l,容易发现如果依次加入右边的每一个数,当前的 LCM 要么不变要么至少 ×2,等价于对于一个左端点只有 logV 个可能的 LCM(V 为值域)。
这个时候,可以考虑从右向左依次枚举 l,每次只需要把上一轮所有 LCM 与当前的 ai 重新计算 LCM 即可。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
typedef long long LL;
const int N = 3e5+10;
int n;
LL a[N];
LL gcd(LL a , LL b) {
if(!b) return a;
return gcd(b , a%b);
}
LL lcm(LL a , LL b) {
return a/gcd(a,b)*b;
}
void slove() {
scanf("%d" , &n);
for(int i = 1 ; i <= n ; i ++)
scanf("%lld" , &a[i]);
set<LL> st , ans;
for(int i = n ; i >= 1 ; i --) {
set<LL> tmp;
for(auto j : st)
if(lcm(j , a[i]) <= 4256233)
tmp.insert(lcm(j , a[i]));
tmp.insert(a[i]);
swap(st , tmp);
for(auto j : st)
ans.insert(j);
}
LL last = 0 , res = -1;
for(auto i : ans)
if(i > last+1) {
res = last+1; break;
} else {
last = i;
}
printf("%lld\n" , res==-1 ? last+1 : res);
return;
}
int main() {
int T; scanf("%d" , &T);
while(T --) slove();
return 0;
}