算法板子：容斥原理——求出 1∼n 中能被质数 p1,p2,…,pm 中的至少一个数整除的整数有多少个

1. 题目要点

1. 设：求1~10中能被质数2和3中至少一个数整除的数有多少个。1~10中能被质数2整除的数的集合记为S1={2,4,6,8,10}，能被质数3整除的数的集合记为S2={3,6,9}，能同时被质数2和3整数的数的集合为S1∩S2={6}

2. 这道题的目的是求S1∪S2∪S3这个集合的元素个数，也就是求交集的个数的交错和。

3. 集合使用二进制标识：S1集合用二进制位001标识; S2集合用二进制位010标识; S1∩S2交集集合用011来标识。
4. 求每个集合的元素个数：S1集合的元素个数为n/p1，也就是10/2=5; S2集合的元素个数为n/p2，也就是10/3=3; S3集合的元素个数为n/(p1*p2)，也就是10/(2*3)=1

2. 代码

#include <iostream>
using namespace std;const int N = 20;// p是质数数组，存储输入样例中给出的所有质数
int p[N];
int n, m;int calc()
{int res = 0;// 枚举所有的集合; m是2，有两个质数，1左移两位是二进制100代表十进制4，也就是说外层循环枚举了二进制001、010、011，也就是枚举了三个集合for (int i = 1; i < 1 << m; i ++ ){int t = 1, sign = -1;// 得到求当前集合个数时的分母tfor (int j = 0; j < m; j ++ ){// 得到当前集合的二进制表示if (i & 1 << j){if (1LL * t * p[j] > n) {t = 0;break;}t *= p[j], sign = -sign;}}// 当前集合的个数为n/tif (t) res += n / t * sign;}return res;
}int main()
{cin >> n >> m;// 初始化质数数组pfor (int i = 0; i < m; i ++ ) cin >> p[i];cout << calc() << endl;return 0;
}