AcWing,890.能被整除的数
给定一个整数
n
n
n 和
m
m
m 个不同的质数
p
1
,
p
2
,
…
,
p
m
p_{1},p_{2},…,p_{m}
p1,p2,…,pm。
请你求出 1 ∼ n 1∼n 1∼n 中能被 p 1 , p 2 , … , p m p_{1},p_{2},…,p_{m} p1,p2,…,pm 中的至少一个数整除的整数有多少个。
输入格式
第一行包含整数
n
n
n 和
m
m
m。
第二行包含 m m m 个质数。
输出格式
输出一个整数,表示满足条件的整数的个数。
数据范围
1
≤
m
≤
16
,
1
≤
n
,
p
i
≤
109
1≤m≤16,1≤n,p_{i}≤109
1≤m≤16,1≤n,pi≤109
输入样例:
10 2
2 3
输出样例:
7
容斥原理:
假如我们现在有一个韦恩图,如果要不重不漏的表示出整个集合的面积(即三个集合的元素个数):
这就是一个基础的容斥原理,推广到n个圆的维恩图的话:
1个圆自己的-每2个圆相交的+有3个圆相交的-有4个圆相交的+…
且观察可知选偶数个集合的时候是负的,而选奇数个集合时是正的
对于这道题,我们要求个数时,就可以用 S 1 S_{1} S1表示1到n中能被 p 1 p_{1} p1整除的数,然后 S 2 S_{2} S2表示1到n中能被 p 2 p_{2} p2整除的数…让我们求个数的时候,就可以用容斥原理来求
以 S p S_{p} Sp表示1到n中能被p整除的个数,即是p的倍数的个数有多少,那么 S p = [ n p ] S_{p}=[\frac{n}{p}] Sp=[pn]
有多个集合相交的部分,即求能够被 p 1 , p 2 , p 3 . . . p_{1},p_{2},p_{3}... p1,p2,p3...等整除的数有多少时,表示为[ n p 1 ∗ p 2 ∗ . . . ∗ p k \frac{n}{p_{1}*p_{2}*...*p_{k}} p1∗p2∗...∗pkn]
为什么下取整? 因为有时候n可能不能整除p,则下取整可以保证取到最大的那个与p成倍数的数
用二进制数和位运算方法来枚举选法,从1枚举到2n,用每一位是1还是0来代表选法
此处容斥原理体现为:这里选的每一个数都相当于一个小集合,集合数代表的便是选的数的个数
代码:
#include<iostream>
using namespace std;
const int N = 20;
int n, m;
int p[N];
int main() {
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枚举到2的m次方-1个选法
int t = 1, cnt = 0; //t表示当前质数的乘积,cnt表示集合个数
for(int j = 0;j < m;j++) //枚举m个质数
if (i >> j & 1) { //如果当前这一位是1,即选上了
cnt++; //集合数加1
//如果按i这种选法乘过之后,发现大于n了,那么就代表这种选法不成立
//在这个情况下无法实现被这些选上的质数整除
//相反如果乘过这些质数后小于n,那么就说明这些数是可以把1到n中的数整除的
if ((long long)t * p[j] > n) { //如果大于n就不用算了
t = -1;
break;
}
t *= p[j];
}
if (t != -1) { //如果没有大于n
if (cnt % 2) res += n / t; //如果有奇数个集合那么加上
else res -= n / t; //如果有偶数个集合那么减去
}
}
cout << res << endl;
return 0;
}