题解：CF1699E Three Days Grace

//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
*/