解题思路

子序列的最大公约数大于 1，意味着存在某个质数 $p$ 整除该子序列的所有元素。因此最长长度等于：对每个质数 $p$ ，序列中能被 $p$ 整除的元素个数（计重）的最大值。记该个数为 $\mathrm{cover}[p]$ ，则

L=\max_{p\text{ 为质数}}\mathrm{cover}[p].

方案按多重集合判重：

题目内容

有一条长度为 $n$ 的零件编号序列 $a_1, a_2, \ldots, a_n$ 。需要选出一条最大公约数不为 1 的子序列，并希望它尽可能长；同时还要统计这种最长子序列有多少种。

若两条子序列所含元素的多重集合相同，则视为同一种方案（不区分下标，只按取值及出现次数判断）。

子序列指从原序列中删除任意个（可以为零）元素后，保持剩余元素相对顺序得到的序列。最大公约数指若干整数共有约数中的最大者。

题目保证序列不全为 1。序列长度与每个编号均不超过 $2 \times 10^6$ 。