CF1834E MEX of LCM

· · 个人记录

链接：

洛谷
cf

MEX of LCM

给定一个长度为 n 的序列 a，一个正整数 x 被称为「可爱的」，当且仅当在序列 a 中，不存在一个子段所有元素的最小公倍数等于 x。求最小的「可爱数」。

以下均为正解 - solution 2 容易发现，在左端点固定的时候，若右端点向右移动，则区间的 $\operatorname{lcm}$ 值要么不变，要么至少乘 $2$。而对于一个质数不可能陈为区间的最小公倍数，因此答案的上界为第 $3e5+1$ 个质数，$4256233$。 因此当左端点固定的时候，有贡献的只有 $\log V$ 个。 因此可以固定左端点，维护区间，并维护可能有用的 $\operatorname{lcm}$，以及不同值。 用 $3$ 个 $set$ 维护即可。 复杂度是 $O(n \log V \log n) 
#include<iostream>
#include<set>
using namespace std;
const int N=3e5+9;
set<int> ans,interval,temp;
int n,T;
int a[N];
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
long long lcm(int a,int b){
    return 1ll*a*b/gcd(a,b);
}
int main(){
    scanf("%d",&T);
    while(T--){
        temp.clear();
        interval.clear();
        ans.clear();
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",a+i);
        }
        for(int i=1;i<=n;i++){
            temp.clear();
            temp.insert(a[i]);
            for(auto j:interval){
                int LCM=lcm(a[i],j);
                if(LCM>5e6) continue;
                temp.insert(LCM);
            }
            interval.clear();
            for(auto j:temp){
                interval.insert(j);
                ans.insert(j);
            }
        }
        for(int i=1;i<=5e6;i++){
            if(ans.find(i)==ans.end()){
                printf("%d\n",i);
                break;
            }
        }
    }
    return 0;
}

优化掉了求最大公约数的复杂度，是通过势能分析优化掉的，但是笔者没太理解。

#include<bits/stdc++.h>
using namespace std;

const int N = 300010;
int t, n, a[N], f[100], cnt, lcm[100], idx, ggcd, book[N * 2 + 10];
const int SIZE = 1 << 14;   char buf[SIZE], *bgn = buf, *til = buf;
char getc()
{   
    if(bgn == til)  bgn = buf, til = buf + fread(buf, 1, SIZE, stdin);
    return bgn == til ? EOF : *bgn++; 
}
inline int read()
{
    char ch = getc();   int x = 0;
    while(ch < '0' || ch > '9') ch = getc();
    while(ch >= '0' && ch <= '9')   x = (x << 1) + (x << 3) + ch - '0', ch = getc();
    return x;
}
inline void print(int x)
{
    if(x / 10)  print(x / 10);
    putchar(x % 10 + '0');
}
int gcd(int a, int b)   {return b ? gcd(b, a % b) : a;} 
int main()
{
    t = read();
    while(t--)
    {
        n = read();
        for(int i = 1; i <= n; ++i) a[i] = read();
        for(int i = 1; i <= n * 2 + 1; ++i) book[i] = 0;
        cnt = 0;
        if(a[n] <= n * 2 + 1)   book[a[n]] = 1, f[++cnt] = a[n];
        else    f[++cnt] = 1;
        for(int i = n - 1; i > 0; --i)
        {
            for(int j = 1; j <= cnt; ++j)   lcm[j] = f[j];
            idx = 0, ggcd = a[i]; 
            for(int j = 1; j <= cnt; ++j) // 后缀长度逐渐减小，后面的 lcm 是前面的因数
            { 
                ggcd = gcd(ggcd, lcm[j]); // 均摊求 gcd 的复杂度，因为 gcd 只会减小
                if(1ll * lcm[j] / ggcd * a[i] <= 2ll * n + 1 && lcm[j] / ggcd * a[i] != f[idx]) 
                    f[++idx] = lcm[j] / ggcd * a[i]; // 用后面数结尾的后缀的 lcm 递推前面数的 
            }
            if(f[idx] != a[i] && a[i] <= 2 * n + 1) f[++idx] = a[i];
            cnt = idx;
            for(int j = 1; j <= cnt; ++j)   book[f[j]] = 1;
        }
        for(int i = 1; i <= n * 2 + 1; ++i)
            if(!book[i])
            {
                print(i), putchar('\n');
                break;
            }
    }
    return 0;
}