题目内容

塔子哥是一个喜欢数学和游戏的年轻人。有一天，他发明了一个新的游戏，可以考验人们的智力和数学知识。

这个游戏的规则很简单：给定一个长度为$n$的整数序列$a$和一个正整数$k$，玩家需要从序列$a$中删掉一些数，使得剩下的数的最大公约数等于$k$。例如，如果序列$a$为$[2,4,6,8]$，$k=2$，则玩家可以删掉$4$和$8$，剩下的数为$[2,6]$，它们的最大公约数是$2$。

思路1:数论+动态规划

1.切入点:一个很容易感觉到的,对我们很有启发性的事情

​ 找出所有是$k$的倍数的数，假设总共$x$个。那么算下他们的子集个数$2^{x} - 1$

这就是答案了？并不是！ 这不是"$gcd$恰好等于$k$" 的子集个数，而是"$gcd$是$k$的倍数"的子集个数。观察他们的关系，我们可以发现：

"$gcd$是$k$的倍数"的子集个数 = "$gcd$恰好是k"的子集个数 + "$gcd$恰好是$2k$"的子集个数 + .. + "$gcd$恰好是$ck$"的子集个数