题目描述

难度分:$1700$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 10^5$，$m$之和$\leq 10^5$。

每组数据输入$n(1 \leq n \leq 10^5)$，$m(1 \leq m \leq 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^5)$。

从$a$中选一个子序列$b$，要求$1,2,…,m$中的每个数字$x$，都能在$b$中找到$x$的倍数。输出$max(b)-min(b)$的最小值。

注：子序列不一定连续。

输入样例

3
2 4
3 7
4 2
3 7 2 9
5 7
6 4 3 5 7

输出样例

-1
0
3

算法

双指针

这个题不难，但可能今天放假心野了，被这个多测搞得WA了好多发。先做个预处理，预处理出一个二维数组$factors$，$factors[num]$中是某些$x$，$num$是这些$x$的倍数。做这个预处理需要遍历$x \in [1,N]$（其中$N=10^5$，是题面所给的$a[i]$值域上限），然后从$num=x$开始以步长$x$自增，将$x$追加到$factors[num]$中。

接下来对数组$a$排序去重，开始进行双指针算法，初始化$l=r=0$。每次无脑将$a[r]$的因子$factors[a[r]]$加入窗口哈希表$window$，只要发现$window$中不同因子的个数为$m$，即$window.size()=m$，说明$b$序列选择$a[l…r]$这些元素就能包括$[1,m]$的所有倍数。然后一边收缩窗口左边界$l$，一边用$a[r]-a[l]$更新最小极差。

复杂度分析

时间复杂度

根据调和级数公式$\frac{n}{1}+\frac{n}{2}+…+\frac{n}{n} \rightarrow lnn$，预处理的时间复杂度为$O(NlnN)$。双指针算法的时间复杂度为$O(nlnN)$，后面这个$lnN$是因为所有因子都都会进窗口一次，出窗口一次。

空间复杂度

空间瓶颈在于预处理的$factors$数组，因为多测数组的缘故，直接把整个值域$[1,10^5]$的因子预处理出来再求解多组数据是最划算的。因此，算法的额外空间复杂度为$O(NlnN)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 100010, INF = 1e9;
int T, n, m;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

vector<int> factors[N];
unordered_map<int, int, custom_hash> window;

void add(int index) {
    for(int factor: factors[index]) {
        if(factor <= m) {
            window[factor]++;
        }
    }
}

void erase(int index) {
    for(int factor: factors[index]) {
        if(factor <= m) {
            window[factor]--;
            if(window[factor] == 0) window.erase(factor);
        }
    }
}

void init() {
    for(int x = 1; x <= N - 10; x++) {
        for(int num = x; num <= N - 10; num += x) {
            factors[num].push_back(x);
        }
    }
}

int main() {
    scanf("%d", &T);
    if(factors[1].empty()) {
        init();
    }
    for(int cases = 1; cases <= T; cases++) {
        scanf("%d%d", &n, &m);
        window.clear();
        vector<int> a;
        for(int i = 1; i <= n; i++) {
            int ai;
            scanf("%d", &ai);
            a.push_back(ai);
        }
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());
        n = a.size();
        int ans = INF;
        for(int l = 0, r = 0; r < n; r++) {
            add(a[r]);
            while(l <= r && m == (int)window.size()) {
                ans = min(ans, a[r] - a[l]);
                erase(a[l]);
                l++;
            }
        }
        if(ans == INF) ans = -1;
        printf("%d\n", ans);
    }
    return 0;
}