Quiz Master

题意翻译

给定一个长度为 $n$ 的正整数序列 $a$，以及一个正整数 $m$。在序列 $a$ 中选出一个长度为 $m$ 子序列（**不是子段**） $b$ ，$\forall i \in [1, m] ,\exists b_j, b_j$ 能被 $i$ 整除。 求所有满足条件的序列 $b$ 的极差（最大值于最小值的差）的最小值；若无满足条件序列 $b$ ，输出 $-1$ 。

题目描述

A school has to decide on its team for an international quiz. There are $ n $ students in the school. We can describe the students using an array $ a $ where $ a_i $ is the smartness of the $ i $ -th ( $ 1 \le i \le n $ ) student. There are $ m $ topics $ 1, 2, 3, \ldots, m $ from which the quiz questions will be formed. The $ i $ -th student is considered proficient in a topic $ T $ if $ (a_i \bmod T) = 0 $ . Otherwise, he is a rookie in that topic. We say that a team of students is collectively proficient in all the topics if for every topic there is a member of the team proficient in this topic. Find a team that is collectively proficient in all the topics such that the maximum difference between the smartness of any two students in that team is minimized. Output this difference.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains $ n $ and $ m $ ( $ 1 \le n,m \le 10^5 $ ). The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^5 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ . It is guaranteed that the sum of $ m $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case, print the answer on a new line. If there is no solution, output $ -1 $ .

输入输出样例

输入样例 #1

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

输出样例 #1

-1
0
3

说明

In the first test case, we have participants with smartnesses $ 3 $ and $ 7 $ , and $ m = 4 $ . Thus, there is no student with smartness divisible by $ 2 $ . Since $ 2 \leq m $ , there is no way to choose a team. In the second test case, we can select the participant with smartness $ 2 $ to be the only one on the team. This way the team will be collectively proficient in both topics $ 1 $ and $ 2 $ . In the third test case, consider the team with participants of smartnesses $ 4, 5, 6, 7 $ . This way the team will be collectively proficient in all topics $ 1, 2, \ldots, 7 $ .

**题意翻译**

给定一个长度为 $ n $ 的正整数序列 $ a $，以及一个正整数 $ m $。在序列 $ a $ 中选出一个长度为 $ m $ 的子序列（**不是子段**） $ b $，使得对于所有的 $ i \in [1, m] $，都存在一个 $ b_j $ 能被 $ i $ 整除。

求所有满足条件的序列 $ b $ 的极差（最大值与最小值的差）的最小值；若无满足条件的序列 $ b $，则输出 $ -1 $。

**题目描述**

一所学校需要决定其国际问答比赛的小组。学校有 $ n $ 名学生。我们可以用一个数组 $ a $ 来描述学生，其中 $ a_i $ 是第 $ i $（$ 1 \le i \le n $）名学生的聪明度。

比赛的问题将来自 $ m $ 个主题 $ 1, 2, 3, \ldots, m $。如果 $ (a_i \bmod T) = 0 $，则第 $ i $ 名学生在主题 $ T $ 上被认为是熟练的。否则，在这个主题上他就是新手。

如果我们说一个学生小组在所有主题上都有熟练的成员，那么就找到了这样一个小组。

找出这样一个在所有主题上都有熟练成员的小组，使得该小组成员聪明度的最大差异最小。输出这个差异。

**输入输出格式**

**输入格式**

每个测试包含多个测试案例。第一行包含测试案例的数量 $ t $（$ 1 \le t \le 10^4 $）。测试案例的描述如下。

每个测试案例的第一行包含 $ n $ 和 $ m $（$ 1 \le n, m \le 10^5 $）。

每个测试案例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \le a_i \le 10^5 $）。

保证所有测试案例中 $ n $ 的总和不超过 $ 10^5 $。

保证所有测试案例中 $ m $ 的总和不超过 $ 10^5 $。

**输出格式**

对于每个测试案例，在一行中输出答案。如果没有解决方案，输出 $ -1 $。

**输入输出样例**

**输入样例 #1**
```
3
2 4
3 7
4 2
3 7 2 9
5 7
6 4 3 5 7
```

**输出样例 #1**
```
-1
0
3
```

**说明**

在第一个测试案例中，我们有聪明度为 $ 3 $ 和 $ 7 $ 的参与者，且 $ m = 4 $。因此，没有聪明度能被 $ 2 $ 整除的学生。由于 $ 2 \leq m $，所以无法选择一个小组。

在第二个测试案例中，我们可以选择聪明度为 $ 2 $ 的参与者作为小组的唯一成员。这样小组将在主题 $ 1 $ 和 $ 2 $ 上都有熟练的成员。

在第三个测试案例中，考虑聪明度为 $ 4, 5, 6, 7 $ 的小组。这样小组将在所有主题 $ 1, 2, \ldots, 7 $ 上都有熟练的成员。**题意翻译** 给定一个长度为 $ n $ 的正整数序列 $ a $，以及一个正整数 $ m $。在序列 $ a $ 中选出一个长度为 $ m $ 的子序列（**不是子段**） $ b $，使得对于所有的 $ i \in [1, m] $，都存在一个 $ b_j $ 能被 $ i $ 整除。 求所有满足条件的序列 $ b $ 的极差（最大值与最小值的差）的最小值；若无满足条件的序列 $ b $，则输出 $ -1 $。 **题目描述** 一所学校需要决定其国际问答比赛的小组。学校有 $ n $ 名学生。我们可以用一个数组 $ a $ 来描述学生，其中 $ a_i $ 是第 $ i $（$ 1 \le i \le n $）名学生的聪明度。 比赛的问题将来自 $ m $ 个主题 $ 1, 2, 3, \ldots, m $。如果 $ (a_i \bmod T) = 0 $，则第 $ i $ 名学生在主题 $ T $ 上被认为是熟练的。否则，在这个主题上他就是新手。 如果我们说一个学生小组在所有主题上都有熟练的成员，那么就找到了这样一个小组。 找出这样一个在所有主题上都有熟练成员的小组，使得该小组成员聪明度的最大差异最小。输出这个差异。 **输入输出格式** **输入格式** 每个测试包含多个测试案例。第一行包含测试案例的数量 $ t $（$ 1 \le t \le 10^4 $）。测试案例的描述如下。 每个测试案例的第一行包含 $ n $ 和 $ m $（$ 1 \le n, m \le 10^5 $）。 每个测试案例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \le a_i \le 10^5 $）。 保证所有测试案例中 $ n $ 的总和不超过 $ 10^5 $。 保证所有测试案例中 $ m $ 的总和不超过 $ 10^5 $。 **输出格式** 对于每个测试案例，在一行中输出答案。如果没有解决方案，输出 $ -1 $。 **输入输出样例** **输入样例 #1** ``` 3 2 4 3 7 4 2 3 7 2 9 5 7 6 4 3 5 7 ``` **输出样例 #1** ``` -1 0 3 ``` **说明** 在第一个测试案例中，我们有聪明度为 $ 3 $ 和 $ 7 $ 的参与者，且 $ m = 4 $。因此，没有聪明度能被 $ 2 $ 整除的学生。由于 $ 2 \leq m $，所以无法选择一个小组。 在第二个测试案例中，我们可以选择聪明度为 $ 2 $ 的参与者作为小组的唯一成员。这样小组将在主题 $ 1 $ 和 $ 2 $ 上都有熟练的成员。 在第三个测试案例中，考虑聪明度为 $ 4, 5, 6, 7 $ 的小组。这样小组将在所有主题 $ 1, 2, \ldots, 7 $ 上都有熟练的成员。