题解：CF1699E Three Days Grace

cvd420 · 2025-03-29 11:08:31 · 题解

两个 log 无脑做法

朴素 dp 是显然的，具体可以看看第一篇题解，这里不再赘述。

由于 CF 机子很快，并不需要第二个性质，直接上线段树维护最大值就能过了。

code

//created by fqr & cyx in 2025
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define ll long long
#define pb emplace_back
int ff,Ch;
template <typename T> inline void rd(T &x) {
    x=0,ff=1,Ch=getchar();
    while((Ch<'0'||Ch>'9') && Ch!='-') Ch=getchar();
    if(Ch=='-')Ch=getchar(),ff=-1;
    while(Ch>='0' && Ch<='9') {
        x=(x<<1)+(x<<3)+Ch-'0';
        Ch=getchar();
    }
    x*=ff;
}
template <typename T,typename ...Args> inline void rd(T &x,Args &...args) {
    rd(x), rd(args...);
}
using namespace std;
const int N=5e6+5;
int n,m;
int a[N]; 
namespace sgt {
    #define ls x<<1
    #define rs x<<1|1
    int mx[N<<2];
    void build(int x,int l,int r,vector<int> &cnt) {
        if(l==r) return mx[x]=cnt[l]?1e9:0,void();
        int mid=l+r>>1;
        build(ls,l,mid,cnt),build(rs,mid+1,r,cnt);
        mx[x]=max(mx[ls],mx[rs]);
    }
    void upd(int x,int l,int r,int pos,int val) {
        if(l==r) return mx[x]=val,void();
        int mid=l+r>>1;
        if(pos<=mid) upd(ls,l,mid,pos,val);
        else upd(rs,mid+1,r,pos,val);
        mx[x]=max(mx[ls],mx[rs]);
    }
}
void Solve() {
    rd(n),rd(m);
    vector<int> cnt(m+1),dp(m+1);
    for(int i=1; i<=n; i++)
        rd(a[i]),cnt[a[i]]++;
    sgt::build(1,1,m,cnt);
    int ans=1e9;
    for(int i=m; i>=1; i--) {
//      dp[i]=i;
//      for(int j=1; j<=m; j++) {
//          if(j%i==0 && i*i<=j)
//              dp[j]=min(dp[j],dp[j/i]);       
//          if(cnt[j]) mx=max(mx,dp[j]);
//      }
        dp[i]=i;
        if(cnt[i]) sgt::upd(1,1,m,i,dp[i]);
        if(1ll*i*i<=m) {
            for(int j=i*i; j<=m; j+=i) {
                if(cnt[j] && dp[j]>dp[j/i]) sgt::upd(1,1,m,j,dp[j/i]);
                dp[j]=min(dp[j],dp[j/i]);
            }
        }
//      cout<<"!" <<sgt::mx[1]<<'\n';
        ans=min(ans,sgt::mx[1]-i);
    }
    printf("%d\n",ans);
}
signed main() {
#ifdef LOCAL
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
#endif
    int T;
    rd(T);
    while(T--) Solve();
    return 0;
}
/*
dp[i][j]将数字j拆成>=i的数后最大值的最小值 
4
5 10
2 4 2 4 2
3 50
12 2 3
2 40
6 35
2 5
1 5
*/