神仙题.大概是一篇只有做法没有思路的题解..
显然这个题 $\gcd > 1$ 就是想建补图.然后问题就变成了选出一个点集使得大小正好为 $k$ 且要么每个点都在导出子图里有边,要么所有点都是孤立点.构造一组方案即可.
需要注意的是第二种情况,如果可以找到一个 $\ge k$ 的独立集,那么只需要保留 $k$ 个点即可.
首先要会求所有点的度数.不难发现 $a_i$ 的度数是
其中 $occ[k]$ 是 $k$ 这个数在 $A$ 中的出现次数.这个东西可以通过把所有数变成 square free 之后集合枚举,并且预处理 $G[t] = \sum_{j|t} occ[j]$,算出所有数的度数的时间是 $O(2^8 n