数学知识——容斥原理

1. 容斥原理
   |AUBUC| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|
   |A|表示集合A中元素的个数

推广：

2. 例题：能被整除的数

给定一个整数n和m个不同的质数p₁,p₂,…,p_m。

请你求出1~ n中能被p₁,p₂,…,p_m中的至少一个数整除的整数有多少个。

输入格式
第一行包含整数n和m。

第二行包含m个质数。

输出格式
输出一个整数，表示满足条件的整数的个数。

数据范围
1≤m≤16,
1≤n,pi≤10⁹
输入样例：
10 2
2 3
输出样例：
7

#include
#includeusing namespace std;
typedef long long LL;const int N = 20;int p[N]; // 存储题目中给定的质数int main()
{int n, m;cin >> n >> m;for(int i = 0; i < m; i++) cin >> p[i];int res = 0;for(int i = 1; i < 1 << m; i++)  // 1<{int t = 1, cnt = 0; // t 表示分母将质数相乘的结果，cnt表示所选中的集合的个数for(int j = 0; j < m; j++)if(i >> j & 1)  // 如果i的二进制表示中的第j+1位是1则表示选中第j+1个质数{if(t * p[j] > n) //如果分母大于n了就结束{t = -1; break;}t *= p[j];cnt ++;}if(t != -1) {if(cnt % 2) res += n / t;else res -= n/t;}}cout << res << endl;return 0;
}					

算法思路：1~ n中含有p的倍数的个数是[n/p]，所以把n/p_i看|S_i|，题目要求的即|S₁+S₂+ …+S_m|,利用容斥原理求解

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！