Type: Default 1000ms 256MiB

k -- GCD 可分数列

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

形式化地,设

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

表示 a1,a2,a3,⋯ ,ana_1,a_2,a_3,\cdots,a_n 的最大公因数,定义 gcd⁡(a)=a\gcd(a)=a。数字 bi,jb_{i,j} 表示分割后的第 ii 段的第 jj 个数,设

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

求 VV 最大可能值。

输入描述

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

第一行输入 nn 个空格隔开的整数 aia_i 表示数列的数字,满足 1⩽ai⩽1×1091\leqslant a_i \leqslant 1\times10^9。

输出描述

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

样例

5 4
1 14 514 1919 810
1
4 3
32 24 36 33
12