CF1834E MEX of LCM 题解

感谢 @llingy 和 @LRC0511 大佬！

题意简述

你有 n 个正整数 a_i(1\leq a_i \leq 10^9)，你需要找到最小的一个正整数 x，使得不存在任一区间 [l,r] 满足 \operatorname{lcm}_{l\leq i \leq r}\{a_i\} = x。

题解

容易发现，在左端点固定的时候，若右端点向右移动，则区间的 \operatorname{lcm} 值要么不变，要么至少乘 2。而对于一个质数，它不可能成为任意两个与它不等的数的 \operatorname{lcm}，而第 3\times 10^5+1 个是 4256233，所以在所有区间的 \operatorname{lcm} 中，那些大于 4256233 的是没有用的。因此，记 V=4256233，则当左端点固定的时候，不同的有用 \operatorname{lcm} 只有 \log V 个。

考虑从右向左移动移动左端点，并且维护以当前点为左端点的不同 \operatorname{lcm}。具体地，可以用两个 set A,B 分别维护当前存在的不同 \operatorname{lcm} 和所有可能有用的 \operatorname{lcm}，左端点左移到 i 的时候，需要将 a_i 放入 A，并遍历 A 中本来就存在的区间，对 a_i 取 \operatorname{lcm} 后重新放入 A。每次更新完之后，就把当前 A 中的元素放入 B 中。最后对 B 中的元素求 \operatorname{mex} 即可。

时间复杂度 O(n\log^2V)

评测记录：CF & 洛谷

Code:

#include <bits/stdc++.h>
using namespace std;
namespace Kycida{
using ll = long long;
const int N = 114.5e4;
set <ll> myset , tmp , tmptmp;
int n , a[N];
ll lcm(ll x , ll j){return x * j / __gcd(x , j);}
int main()
{
    int T; cin >> T;
    while(T--) {
        cin >> n; myset.clear(); tmp.clear();
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for (int i = n; i > 0; i--) {
            tmptmp.clear(); tmptmp.insert(a[i]);
            for (auto j : tmp) {
                ll tt = lcm(j , a[i]);
                if (tt < 5e6) {
                    tmptmp.insert(tt);
                }
            }
            tmp.clear();
            for (auto j : tmptmp) {
                tmp.insert(j);
                myset.insert(j);
            }
        }
        int ans = 1;
        for (; myset.count(ans); ans++);
        cout << ans << '\n';
    }
    return 0;
}
}int main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    return Kycida :: main();
}