容差原则 - 数学知识 (c++)
最编程
2024-07-05 08:32:58
...
容斥原理
可以描述如下:
要计算几个集合并集的大小,我们要先将所有单个集合的大小计算出来,然后减去所有两个集合相交的部分,再加回所有三个集合相交的部分,再减去所有四个集合相交的部分,依此类推,一直计算到所有集合相交的部分。
用维恩图来表示集合A、B和C:
经典例题
AcWing 890. 能被整除的数
给定一个整数n和m个不同的质数p1,p2,…,pm。
请你求出1~n中能被p1,p2,…,pm中的至少一个数整除的整数有多少个。
输入格式
第一行包含整数n和m。
第二行包含m个质数。
输出格式
输出一个整数,表示满足条件的整数的个数。
数据范围
1≤m≤16,
1≤n,pi≤109
输入样例:
10 2
2 3
输出样例:
7
#include <iostream>
#include <algorithm>
using 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 ++ ) // i<1<<m 组合数 2^m-1
{
int t = 1, s = 0;//s用来记录这种方案,选择的数的个数,从而判断应该加还是减;t存累乘的结果
for (int j = 0; j < m; j ++ )//遍历二进制的每一位
if (i >> j & 1)//判断二进制第j位是否存在
{
if ((LL)t * p[j] > n)//这里要加long 否则会溢出
{
t = -1;
break;
}
t *= p[j];
s ++ ;
}//为这种方案求出一个总乘积t
if (t != -1)
{
if (s % 2) res += n / t;//奇数个数,说明要加
else res -= n / t;//偶数个数,说明要减
}
}
cout << res << endl;
return 0;
}
上一篇: 容斥原理