B. k -- GCD 可分数列

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你正在参加国际连续分隔大赛(International Continous Partition Contest, ICPC)，给定一个数列将其分割成 $k$ 段，记每段价值为该段所有数字的 GCD 值；求所有段价值中最小值的最大可能值。

形式化地，设

$$\operatorname{gcd}_{i=1}^n\left\{ a_i \right\} := \operatorname{gcd}\left( a_1,a_2,a_3,\cdots,a_n \right)$$

表示 $a_1,a_2,a_3,\cdots,a_n$ 的最大公因数，定义 $\gcd(a)=a$ 。数字 $b_{i,j}$ 表示分割后的第 $i$ 段的第 $j$ 个数，设

$$V=\operatorname{min}_{i=1}^k\left[ \operatorname{gcd}_{j=1}^n\left( b_{i,j} \right) \right]$$

求 $V$ 最大可能值。

第一行输入两个空格隔开的整数 $n,k$ 表示数列中数字的个数 $n$ 与段数 $k$ ，满足 $1\leqslant k\leqslant n \leqslant 1\times 10^4$ 。

第一行输入 $n$ 个空格隔开的整数 $a_i$ 表示数列的数字，满足 $1\leqslant a_i \leqslant 1\times10^9$ 。

输出一个整数表示所有段价值中最小值的最大可能值。

5 4
1 14 514 1919 810

4 3
32 24 36 33