解题思路
要求“最大元素的最小可能取值”，可以二分这个最大值。
假设当前二分值为 x，那么只能选取满足 ai≤x 的元素。问题就变成：
在这些元素中，是否存在长度至少为 k 的子序列，使得相邻两个元素的 gcd>1。
对于一个数 ai，如果它能接在前一个数后面，说明二者至少有一个公共质因子。因此可以把每个数拆成不同质因子。
P4980.第3题-寻找满足条件的最优子序列
题目内容
给定长度为 n 的数组 a，小C想选出一个长度为 k 的子序列。
所选子序列需满足相邻两个元素的 gcd 不为 1。具体地，若选取下标序列 i1<i2<⋯<ik，则需要满足：gcd(aij,aij+1)>1（1≤j<k）。
在所有满足上述条件的子序列中，求最大元素的最小可能取值。
如果不存在满足条件的子序列，则输出 −1。
【名词解释】
- 子序列：从原序列中删除任意个（可以为零）元素得到的新序列。
- gcd：即最大公因数，指两个整数共有约数中最大的一个。例如，gcd(12,30)=6。
输入描述
第一行输入两个整数 n,k（1≤k≤n；2≤n≤2×105），分别表示数组长度和所选子序列长度。
第二行输入 n 个整数 a1,a2,…,an（1≤ai≤109），表示数组元素的值。
输出描述
输出一个整数，表示满足条件的子序列中，最大元素的最小可能取值。
如果不存在满足条件的子序列，则输出 −1。
样例1
输入
5 3
2 4 3 9 6
输出
6
说明
- 可选下标 [1,2,5] 对应元素 {2,4,6}，此时 gcd(2,4)=2>1，gcd(4,6)=2>1，最大值为 6。
- 可知没有更小的最大值，因此输出 6。
样例2
输入
5 2
5 7 11 13 17
输出
-1
说明
在这个样例中，数组中任意两个元素的 gcd 均为 1，无法选出符合条件的子序列，因此输出 −1。
