# How many integers can you find（容斥原理） - HDU 1796

n(A∪B)=n(A)+n(B) -n(A∩B)

Problem Description

Now you get a number N, and a M-integers set, you should find out how many integers which are small than N, that they can divided exactly by any integers in the set. For example, N=12, and M-integer set is {2,3}, so there is another set {2,3,4,6,8,9,10}, all the integers of the set can be divided exactly by 2 or 3. As a result, you just output the number 7.

Input

There are a lot of cases. For each case, the first line contains two integers N and M. The follow line contains the M integers, and all of them are different from each other. 0<N<2^31,0<M<=10, and the M integer are non-negative and won’t exceed 20.

Output

For each case, output the number.

Sample Input

12 2

2 3

Sample Output

7

1、对于数字N，用M中的每个数去整除，然后计算数量，肯定有重复的。

2、通过容斥原理，可以知道n(A∪B∪C...)=n(A)+n(B)+n(C)...-n(A∩B)-n(A∩C)-n(B∩C)...+n(A∩B∩C)...

3、本题性能优化主要有3处

4、注释比代码还多，与前面那个组合的问题有点相似，数学题目就是这样，难以理解，代码精简，解题的性能差距比较大。

```#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<fstream>
using namespace std;

long long N;
long long s[100];
vector<long long > q;

//求最大公约数
int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}

long long solve(int size)
{
long long ans = 0;
//将符合条件的m个数，看作m位，每位是0或者是1，那么一共有2^m种状态
//1<<x就是2的x次方，如1<<0是2的0次方，1<<1是2的1次方
for (long long i = 1; i < (1 << size); i++)
{
long long p = 1;
int cnt = 0;
for (long long j = 0; j < size; j++)
{
//与操作确定该数字是否参与组合
//比如这里的size为3，那么二进制(1<<size)-1表示为111
//i的值用二进制表示依次为1,10,11,100,101,110,111
//1<<j的值依次为1,10,100
//如果i的值为110，则1<<j在10和100的时候&i就能大于0
if ((1 << j)&i)
{
//计算最小公倍数
//lcm(a,b) = a*b/gcd(a,b)
p = p / gcd(p, q[j]) * q[j];
cnt++;
}
}
//cnt表示组合有几个数，奇数次减去，偶数次加上
//这里为啥是(n-1)/p，比如(n-1)=11，p=2，那么被2分的数字肯定是(n-1)/p
//依次为2、4、6、8、10
if (cnt & 1)
ans += (N - 1) / p;
else
ans -= (N - 1) / p;
}

return ans;
}

//可以将测试数据放在文件里面，便于调试
//fstream ifs("test.txt");
//#define cin ifs

int main()
{
int M = 0;
//输入N和M
while (cin >> N >> M)
{
q.clear();
int flag = 0;
//输入M个数的集合S
for (int i = 0; i < M; i++)
{
cin >> s[i];
}
//排序
sort(s, s + M);
//去掉重复的数，比如2和6，去掉6，注意这一步去重非常影响性能
for (int i = 0; i < M; i++)
{
if (s[i] <= 0)
continue;

for (int j = i + 1; j < M; j++)
{
//是否能够被整除，能够被整除说明不需要参与组合计算
//比如2和6，能被6整除的肯定能被2整除
if (s[j] % s[i] == 0)
s[j] = -1;
}
q.push_back(s[i]);
}
long long ans = solve(q.size());
cout << ans << endl;
}

return 0;
}```

219 篇文章34 人订阅

0 条评论

## 相关文章

41580

30460

30250

8010

32920

### 【学习】视觉直观感受 7 种常用排序算法

10月14日发布《统计世界的十大算法》后，很多朋友在后台询问，哪里有“视觉直观感受 7 种常用排序算法”，今天分享给大家，感谢todayx.org。 1. 快速...

32550

20850

13800

23060

386120