容斥原理

在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为「容斥原理」。

维恩图

求著名的维恩图的面积，就是容斥原理的基本应用。

维恩图是如下所示的一种图：

它由三个圆形组成，并且三个圆均存在交集，那么这时候我们如果想求出红色图形的面积，就可以用三个圆的总面积，减去公共面积。

我们给每个部分一个编号，其中1代表黄色圆形、2代表绿色圆形、3代表蓝色圆形、4表示1和2的交集，5表示1和3的交集、6表示2和3的交集、7表示1和2和3三者的交集。

那么最外圈的红色形状面积显然是1+2+3-4-5-6+7(数字代表图形面积)就能算出来啦。

用自然语言描述就是：

1. 先加起来三个圆；
2. 减去1和2的交集4、减去1和3的交集5、减去2和3的交集6；
3. 而图形7，在第一步被计算了三次，在第二步又被减去三次，所以一来一回相当于没有计算7，但是7显然也是红色形状的组成部分，所以最后再加上7，就得到了红色图形的面积。

n个集合的容斥原理

基于上面的分析，我们用 来表示三个圆形的面积，那么对于红色形状的面积就可以表示成如下形式：

「进一步的，如果我们把3个图形扩展到4个图形呢？」

显然可以有如下表示形式：

「再进一步，如果扩展到n个图形呢？」

「更进一步的，把图形推广到集合，也就是说可以用容斥原理来表示给出集合中所有集合的全部并集。」

我们可以把维恩图中的红色区域表示为三个集合的并集，记为： 。把n个集合的并集表示为： 。

根据前文中三个集合、四个集合求并集的表示形式，进而可以推出n个集合求并集的公式：

实际应用

给定一个整数 n 和 m 个不同的质数 p1,p2,…,pm。

请你求出 1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。

举个例子

给出n=10，两个质数2和3，问题是1~10中有几个数能被2和3中至少一个数整除呢？

列举出1~10，不难发现能被2或3整除的有2,3,4,6,8,9,10，总共7个数。

如何用容斥原理分析呢？

我们先找到能被2整除的数的集合，记作 ，那么很容易知道 是 {2,4,6,8,10}。再找到能被3整除的数的集合，记作 ，那么很容易知道 是{3,6,9}。

用容斥原理就是：
（注意这里的"||"表示集合的个数，而不是绝对值）。

在该问题中，如果用 表示能被 整除的数的集合，那么最终其实就是在求 。

如何能把公式实现出来呢？

首先，要清楚的是，「题目要求，不需要知道每个集合中具体的数是什么，只需要知道每个集合中有多少数（集合的大小）」。显然，集合的大小就是n/pi，例如：10中有多少个2，既10/2=5；10中有多少个3，既10/3=3。

其次，我们如何知道，这5个数和3个数之间有几个数是有交集的呢？

这里我们就要注意到题目的一个重要条件，既「给出 m 个不同的质数 p1,p2,…,pm」。p全部是质数，说明「它们的最小公倍数就是他们的乘积」，而他们的交集就是最小公倍数在 n 中的个数。例如：2*3=6则2和3的最小公倍数就是6，用10/6=1就找出来了2和3的交集的个数。

二进制枚举状态

在本题中，共有m个p，所以会有m个 ，那么我们可以用二进制来枚举出每个集合的状态。

例如，当m=4的时候，需要4个二进制位表示集合，假如当前是1101，则表示选中集合为 （也就是本轮循环需要计算该3个集合）。

用组合数计算枚举的状态总数

如何知道需要枚举多少个二进制位呢？

实我们可以用组合数来表示计算时候每个集合项的选中情况。

第一步中选出所有的集合相加，那么对于某一个集合，共有多少组合项，就是从n个集合中挑出1个，既 ；第二步某两个集合有多少组合项呢？就是从n个集合中挑出2个，既 ，以此类推，最后则是从n个集合中挑出n项，既 。

最后，即是 。表示的是共有n对组合数，每组组合数都有选或者不选两种情况，而其中 只有一种情况就是全不选，所以只有一种情况，因此最后要减一。

因此，我们需要枚举 个不同的集合状态。

Code

输入样例：
10 2
2 3
输出样例：
7

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 20;

int n, m;
int p[N];

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i ++ ) cin >> p[i];
    
    int res = 0;
    // 枚举1 到 111...（m个） 中每个集合的状态
    for (int i = 1; i < 1 << m; i ++ ) {
        // t 表示选中集合对应质数的乘积
        // cnt 表示选中集合的数量
        int t = 1, cnt = 0;
        // 枚举当前选法的每一位
        for (int j = 0; j < m; j ++ ) {
            // 1 表示j代表的集合在本轮被选中
            if (i >> j & 1) {
                // 选中集合++
                cnt ++ ;
                // 如果集合中质数的乘积已经大于n，既n/t=0
                // 说明没有交集元素了，所以break掉。
                if ((LL)t * p[j] > n) {
                    t = -1;
                    break;
                }
                t *= p[j];
            }
        }
        if (t != -1) {
            // 如分析 n/t表示交集个数
            // 本轮集合个数是偶数则加上交集，奇数则减去交集
            if (cnt % 2) res += n  / t;
            else res -= n / t;
        }
    }
    cout << res << endl;
    return 0;
}