题解

思路

设 $c_d$ 为序列中能被 $d$ 整除的元素个数。大小恰为 $k$ 且最大公因数为 $1$ 的子集数为

其中 $A=\max a_i$，$\mu$ 为 Möbius 函数。这是对“所有元素都能被 $d$ 整除”做 Möbius 反演。

只需要检查 $k\le7$。若一个最小合法子集大小为 $m$，那么删除其中任意一个元素后，其余元素的最大公因数都大于 $1$。可以为每个被删除位置选出一个只被该位置破坏的不同质因子，于是某个元素至少含有其余 $m-1$ 个不同质因子。当 $m\ge8$ 时，这个数至少为前七个质数之积 $510510$，超过 $a_i\le300000$，矛盾。

做法

先求整个序列的最大公因数；若不为 $1$，立即输出 $-1$。线性筛求出 $1\ldots A$ 的 Möbius 函数，再用枚举倍数求出所有 $c_d$。依次对 $k=1\ldots7$ 精确计算 $F_k$，第一个正数对应最小答案。

组合数最大为 $\binom{300000}{7}$，可用有符号 128 位整数精确容纳，从而避免模数恰好整除真实方案数造成误判。

子任务 1 可枚举所有子集；子任务 2 可维护每种可能最大公因数对应的最少选择数。

复杂度

时间复杂度为 $O(A\log A+n)$，空间复杂度为 $O(A)$。