CF1834E 题解

Xy_top · 2023-10-11 20:10:47 · 题解

学校里口胡的时候什么性质都发现了，但是懒得往下想了，就想了 3 个 \log 的。（枚举左端点，二分 \operatorname{lcm} 的变化位置，求区间 \operatorname{lcm}）

考虑答案的上界，可以先考虑一个素数什么时候被计入答案，显然是这个数组中出现了这个素数，那么答案的上界就显然是第 300001 个素数。

这个数并不大，也就是 3000000 左右的样子，然后来看 \operatorname{lcm}，每次 \operatorname{lcm} 变化至少乘以 2，\log 3000000 次就超出了答案上界，统计它就没意义了。

于是可以先枚举左端点，然后二分每次 \operatorname{lcm} 的变化位置，再用猫树（目前想不到 O(1) 求区间 \operatorname{lcm} 的办法），这样就是 3 个 \log，无法通过。

考虑由 i+1 为起点所有能凑出的 \operatorname{lcm}（根据刚刚的分析，只有 \log 级别） 再加上 a_i 就能得到以 i 为起点能凑出的所有 \operatorname{lcm}，最后将这些答案都放到 set 里去重，能够做到 O(n\log^2 n)。

代码：

#include <bits/stdc++.h>
#define int long long
#define For(i, a, b) for (int i = (a); i <= (b); i ++)
#define foR(i, a, b) for (int i = (a); i >= (b); i --)
using namespace std;
int n, mex;
int a[300005];
set <int> s, ans, tmp;
int gcd (int x, int y) {
    if (y == 0) return x;
    return gcd (y, x % y);
}
int lcm (int x, int y) {return x * y / gcd (x, y);}
void solve () {
    s.clear ();
    ans.clear ();
    cin >> n;
    For (i, 1, n) cin >> a[i];
    foR (i, n, 1) {
        tmp.clear ();
        for (int j : s) {
            if (lcm (j, a[i]) <= 4256249) tmp.insert (lcm (j, a[i]) );
            ans.insert (j);
        }
        tmp.insert (a[i]);
        swap (s, tmp);
    }
    for (int i : s) ans.insert (i);
    int mex = 1;
    for (int i : ans)
        if (i == mex) ++ mex;
    cout << mex;
}
signed main () {
    int _ = 1;
    cin >> _;
    while (_ --) {
        solve ();
        cout << '\n';
    }
    return 0;
}