由维恩图引入 对于多个圆拼成的一个图形，如果要求他的面积，该过程如下 从前几个可以看出规律： 三个圆覆盖的面积 = 一个圆做组合面积 - 2个圆做组合面积 + 3个圆做组合 - 4个圆做组合 + … + （-1）^ (n - 1) 个圆做组合。可以看到正负号相间。 表示成集合即为：S1∪S2∪S3 = S1 + S2 + S3 - S1 ∩ S2 - S2 ∩ S3 - S1 ∩ S3 + S1 ∩ S2 ∩ S3 三个集合并集的元素个数 = 3个单个个集合的元素个数 - 2个结合交集的元素个数 + 3个结合的交集的元素个数。这个是容斥原理集合表示，总共的项数就是2^n - 1 什么是容斥原理？我们假设一个元素x，出现在了k个集合当中， 1 <= k <= n 这个组合等式一点事等于1的，对集合来说，使用这种方法，对任意元素x只会统计一次。
下面举例使用容斥原理： 时间复杂度：如果使用枚举方法的话，O(N * M);使用容斥原理的话，为O(2^n) 容斥原理需要先定义集合， 定义S2为所有2的倍数的集合，S3为所有3的倍数的集合。1 ~ n中的x倍数的个数等于 n / x个。 如果要求S2∩S3集合中数的个数，因为本题目中的集合都是互质的，因此各个集合是互斥的。S2∩S3集合中的数即6的倍数。推广一下就是求任意多个质数的交集的集合中数的个数就是 n / (X1 * X2 …*Xk) 这道题目就是求解对于n个质数的集合的并集的元素的个数。
对集合的选择，使用二进制来表示，比如001011 当某一位为1的时候表示选择了当前集合，每个二进制数表示的是一种选法。因此如果001011表示选择了6个集合中的三个集合来组合，因此这一项的系数为负。总共是2^6次方种选法。
代码表示：
#include<iostream> #include<algorithm> using namespace std; typedef long long LL; const int N = 20; int p[N], n, m; int main(){ cin >> n >> m; int res = 0; for(int i = 0; i < m; i++) cin >> p[i]; for(int i = 1; i < 1 << m; i++){ int t = 1, cnt = 0; //cnt 表示的是m位为1的个数 for(int j = 0; j < m; j++) { if(i >> j & 1) { cnt++; if((LL)t * p[j] > n) { t = -1; break; } t *= p[j]; } } if(t != -1){ if(cnt % 2) res += n / t; else res -= n / t; } if(i == 0) cout << res << endl; } cout << res << endl; return 0; }