已知存在集合A包含n个整数，从1到n。 存在m个整数a[1..m]。 在集合A中去除这m个整数的的倍数。 输出集合中包含的元素的个数。 输入描述： 第一行输入n，m。(1 <= n <= 1e9, 1 <= m <= 10) 第二行输入m个32位整数。 输出描述： 输出集合中包含元素的个数。 输入样例： 5 2 2 3 输出样例： 2

思路：容斥原理。根据题意，需要求出1到n中的数中不被m个给定数整除的数的个数。不妨设S1为1到n中所有数的集合，S2为所有m个给定数的集合，S3为1到n中所有被其中任意一个给定数整除的数所构成的集合，则题目所求的结果即为S1与S3的差集的大小，即$n-|S3-S1|$。由容斥原理，有$|S3-S1|=\sum_{i=1}^{m}(-1)^{i-1}\sum_{1\leq j_1<j_2<\cdots<j_i\leq m}|S_{j_1,j_2,\cdots,j_i}|$，其中$|S_{j_1,j_2,\cdots,j_i}|$表示1到n中所有被第$j_1,j_2,\cdots,j_i$个给定数整除的数所构成的集合。由此可以得到下列代码。具体实现中，可以利用set来实现集合的差集运算。时间复杂度为O(2^mlogn)。当m很小时，可以通过本题；否则需要使用更高效的算法。

相关问题

已知存在集合A包含n个整数，从1到n。 存在m个整数a[1..m]。 在集合A中去除这m个整数的的倍数。 编写js函数输出集合中包含的元素的个数。 输入描述： 第一行输入n，m。(1 <= n <= 1e9, 1 <= m <= 10) 第二行输入m个32位整数。 输出描述： 输出集合中包含元素的个数。 输入样例： 5 2 2 3 输出样例： 2

解题思路：
将所有要去除的数的倍数标记出来，剩下的数即为集合中包含的元素。可以使用一个长度为n的布尔数组来表示每个位置上的数是否被标记，初始化为false，从小到大遍历每个数，对于每个未被标记的数p，将p的倍数标记为true，最后遍历布尔数组统计未被标记的数的数量即可。

具体实现中，可以考虑对于第i个去除的数，从i*i开始将i的倍数标记为true，因为小于i的i的倍数已经被标记了。此外，可以在遍历时只从1到sqrt(n)进行，因为大于sqrt(n)的i的倍数一定小于n，并且已经被标记了。注意在标记时需要判断是否超出了n的范围。

时间复杂度为O(nloglogn)，空间复杂度为O(n)。

参考代码：

已知一个m*n整数矩阵A和一个m维向量b,0/1整数规划问题是：是否存在其元素属于集合{0，1}的一个n维整数向量使得ax<=b。证明0/1整数规划问题是NP完全的。（提示：约简到3-CNF-SAT)

要证明0/1整数规划问题是NP完全的，需要证明两个事实：

1. 0/1整数规划问题属于NP问题集合中；
2. 0/1整数规划问题可以被约简到3-CNF-SAT问题。

首先，我们证明0/1整数规划问题属于NP问题集合中。给定一个0/1整数规划问题，如果存在一个解向量x，使得ax<=b，那么我们可以在多项式时间内验证这个解向量是否正确。因此，0/1整数规划问题可以在多项式时间内验证，属于NP问题集合中。

接下来，我们需要将0/1整数规划问题约简到3-CNF-SAT问题。具体来说，我们需要将一个0/1整数规划问题转化为一个等价的3-CNF-SAT问题，并且这个转化过程可以在多项式时间内完成。

考虑如何将一个0/1整数规划问题转化为一个3-CNF-SAT问题。我们将每个0/1整数规划问题中的变量xi都转换为一个布尔变量yi和它的否定变量yi'，即yi表示xi取值为1，yi'表示xi取值为0。然后，我们将0/1整数规划问题中的每个约束ax<=b都转换为一个3-CNF子句。

具体来说，对于一个约束ax<=b，我们可以将它转换为以下三个子句：

1. 如果aij=0，则必须有yj'=1；
2. 如果aij=1，则必须有yj=1；
3. 如果ax<=b，则必须有∑(aij*yj)<=b。

第一个子句表示如果aij=0，那么yi'必须为真，即xi必须取值为0。第二个子句表示如果aij=1，那么yi必须为真，即xi必须取值为1。第三个子句表示aij*yj的总和不能超过b。

这样，我们就将0/1整数规划问题转化为了一个等价的3-CNF-SAT问题。这个转化过程可以在多项式时间内完成，因此0/1整数规划问题可以被约简到3-CNF-SAT问题。

综上所述，我们证明了0/1整数规划问题是NP完全的，因为它既属于NP问题集合中，又可以被约简到3-CNF-SAT问题。