526互联

Codeforces Round 879 (Div. 2)E. MEX of LCM（数学，数据结构）

发布时间 2023-08-30 10:29:35作者: XiCen

题目链接：https://codeforces.com/contest/1834/problem/E

 

题意：

 

有长度为n的序列，问最小的正整数 x ，对于任意连续的子区间，区间的数的最小公倍数 都不等于 x；

 

分析：

 

首先来分析一下答案的范围是多少；

 

我们可以知道，对于长度 为n 的序列，前 n + 1个素数里面，他至少有一个是不会出现的；

 

然后我们拿筛子跑一遍，发现第 3e5 + 1的素数是 T = 4256233；

 

我们固定右端点，我们发现，如果LCM要增加，那么他一定至少是 乘 2的；

 

所以左边出现的本质不同的LCM 不会多于 log（T）个；

 

故我们可以暴力来跑，用set来维护左边本质不同的LCM；

 

时间复杂度：O（n * log（T）* log（T））；

 

代码：

 

#include<bits/stdc++.h>

#define int long long

const int up = 4256233;

int GCD(int a, int b) {
    return b ? GCD(b, a % b) : a;
}

int LCM(int a, int b) {
    return a * b / GCD(a, b);
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int T;
    std::cin >> T;
    while (T--) {
        int n;
        std::cin >> n;
        std::vector<int> a(n + 1, 0);
        for (int i = 1; i <= n; ++i)std::cin >> a[i];
        std::set<int> ans, now, lst;
        for (int i = 1; i <= n; ++i) {
            now.clear();
            for (auto x: lst) {
                int y = LCM(x, a[i]);
                if (y >= up)continue;
                now.insert(y);
            }
            now.insert(a[i]);
            lst.clear();
            for (auto x: now)lst.insert(x), ans.insert(x);
        }
        int mex = 1;
        for (auto x: ans)if (mex == x)mex++; else break;

        std::cout << mex << "\n";
    }

    return 0;
}

哈哈哈，暴力，水题（bushi：）