P6650 「SWTR-5」Sequence

小 A 有一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$。他可以选择一个区间 $[l,r]$ 满足其最大值与最小值的差不超过 $k$。 他还需找出 $m$ 个**互不相同的整数** $p_1,p_2,\cdots,p_m$，满足： - $m$ 为正整数。 - $\prod\limits_{i=l}^ra_i=\prod\limits_{i=1}^mp_i$。即选择区间的乘积等于这 $m$ 个数的乘积。 - $p_i$ 为一个质数的正整数次幂。 这 $m$ 个数的约数个数之和就是小 A 的得分。帮他求出得分的最大值。

第一行两个整数 $n,k$。 第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 表示这个序列。

一行一个整数表示答案。

「样例说明」 样例 $1$：选择区间 $[1,2]$，再选择 $p_1=2$，$p_2=3$，$p_3=4$，可以达到最大值 $7$，方案不唯一。 样例 $2$：选择区间 $[1,4]$，再选择 $p_1=4$，$p_2=8$，$p_3=3$，$p_4=27$，可以达到最大值 $13$。 「数据范围与约定」 **本题采用捆绑测试**。 - Subtask 1（1 points）：$n=1$ 且 $a_1$ 为质数。 - Subtask 2（9 points）：$n=1$。 - Subtask 3（20 points）：$n\leq 10$，$a_i \leq 20$。 - Subtask 4（13 points）：$n\leq 200$，$a_i \leq 200$。 - Subtask 5（17 points）：$n\leq 2\times 10^3$。 - Subtask 6（15 points）：$a_i$ 为质数。 - Subtask 7（25 points）：无特殊限制。 对于 $100\%$ 的数据：$1 \leq n \leq 10^5$，$2 \leq a_i \leq 10^5$，$0 \leq k \leq 10^5$。 --- 「题目来源」 [Sweet Round 05](https://www.luogu.com.cn/contest/28195) B。 idea & solution：[ET2006](https://www.luogu.com.cn/user/115194)。