Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
3.0 kB
5
Indexable
Never
#include<bits/stdc++.h>
#define pb push_back
#define ll long long int
#define se second
#define fi first
using namespace std;

int dx[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dy[8] = { 0, 0, 1, -1, 1, -1, -1, 1 };

/*#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

typedef tree <
    pair<int ,int>,
    null_type,
    less<pair<int ,int>>,
    rb_tree_tag,
    tree_order_statistics_node_update> ordered_set;
*/

const int mod = 1e9+7;
const int N = 1e5+10;

vector<int>d[N], dd[N];
int cnt[N];

void pre()
{
    for(int i=1;i<N;i++)
    {
        cnt[i] = 0;
        for(int j=i;j<N;j+=i)
        {
            d[i].pb(j);
        }
    }

    for(int i=1;i<N;i++)
    {
        cnt[i] = 0;
        for(int j=i;j<N;j+=i)
        {
            dd[j].pb(i);
        }
    }
}
void solve(int tc)
{
    int n,m,i,j;

    cin>>n>>m;

    int ar[n+5];

    for(i=1;i<=n;i++)
    {
        cin>>ar[i];
        cnt[ar[i]] = 1;
    }

    sort(ar+1, ar+n+1);

    bool f = false;

    for(i=1;i<=m;i++)
    {
        f = false;
        for(auto it: d[i])
        {
            if(cnt[it]==1)
            {
                f = true;
                break;
            }
        }
        if(f==false)
        {
            cout<<-1<<endl;

            for(j=1;j<=n;j++)
            {
                cnt[ar[j]] = 0;
            }
            return;
        }
    }
    for(i=1;i<=n;i++)
    {
        cnt[ar[i]] = 0;
    }

    set<int>st, st1;

    for(i=1;i<=m;i++)
    {
        st1.insert(i);
    }

    int mn = 1e8;

    for(i=1;i<=n;i++)
    {
        for(auto it: dd[ar[i]])
        {
            //cout<<ar[i]<<' '<<it<<endl;
            if(st1.size() && st1.find(it)!=st1.end())
            {
                st1.erase(st1.find(it));
            }
//            if(st1.empty() && st.size())
//            {
//                mn = min(mn, abs(*st.begin()-*st.rbegin()));
//            }
            if(cnt[it]==1)
            {
                if(st.size() && *st.begin()==it)
                {
                    //cout<<it<<endl;
                    st.erase(st.find(it));
                    cnt[it] = 0;
                }
            }

            //for(auto it: st1) cout<<it<<' ';
            //cout<<endl;
        }
        st.insert(ar[i]);
        cnt[ar[i]]=1;

        if(st1.empty() && st.size())
        {
            mn = min(mn, abs(*st.begin()-*st.rbegin()));
        }
    }

    if(st1.size())
    {
        cout<<-1<<endl;

        for(j=1;j<=n;j++)
        {
            cnt[ar[j]] = 0;
        }
        return;
    }

    for(j=1;j<=n;j++)
    {
        cnt[ar[j]] = 0;
    }

    cout<<mn<<endl;
}
int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	pre();

	int tc = 1;
	cin>>tc;

	for(int tt=1;tt<=tc;tt++)
    {
        solve(tt);
    }
	return 0;
}