algorithm - 子集总数

Question

我越来越好奇这个问题了。。

你可以从集合 P = {1, 2, 3, .. n} 中选择一个子集有多少种方法？子集 S 应满足以下条件：

当你选择 x (x ∈ P, x 是集合 P 的一个元素) 来创建 S 时，你不能为 S 选择 a * x 和 b * x。

约束：

1 <= n <= 1000
2 <= a < b <= n
b % a != 0 ( b is not divisible by a)

例子 ：

n = 3 , a = 2, b = 3
so total subsets are 5 ,i.e, {}, {1}, {2}, {3}, {2, 3} 
as if in a particular subset there is 1 so 1*2 = 2 and 1*3 cant be there.
so {1,2}, {1,3} and {1,2,3} can't be there

Answer 1

更新

这与序列 A051026 相关：整数序列在线百科全书 OEIS 中 {1, 2, ..., n} 的原始子序列数。

我认为没有任何简单的方法可以计算条款。甚至递归计算也不是微不足道的，除非什么时候n是素数，其中：

a(n) = 2 * a(n-1) - 1

---

这里的问题和“A051026”都可以被认为是上述序列的泛化的子问题。“A051026”是带有 的实例(a,b,..) = (2,3,4,5...)，例如“所有整数> = 2”。

Answer 2

我相信计算互补会更容易——即不允许的 S 子集的数量。这是S每个子集的数量，至少有一对(a,b)这样a除以b。在计算出该数字 M' 后，只需从 S 的子集总数中减去它，即 2 ⁿ。

现在要计算S不允许的子集的数量，您必须应用包含-排除原则。该解决方案不是很容易实现，但我认为没有替代方法。