题目描述
给定一个整数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
算法1
模板
题解
假设我们现在有5个数,上面分别标号了0,1,2,3,4代表这些小球的权值,现在要像你求出这些小球的权值可以组成的所有情况。
我们用二进制的思维来考虑这个问题,因为有5个数,所以我们用5个比特位来分别标记数存在还是不存在,对于这样一种情况,比如我们现在要选择2,3的倍数,别是2,3,4数,那么我们用二进制1表是当前的数存在,用0表示当前数不存在
二进制下标 4 3 2 1 0
二进制 1 1 1 0 0
小球状态 存在 存在 存在 不存在 bu存在
我们可以用5个比特位来表示这种情况,如果数全部选择的话那么二进制表示就是11111,二进制的11111转化为十进制数字就是31,这个数字正好就是2^5−1,那么我们可以用从0~(2^5−1)这些数表示完所有的选取状态(因为这个范围内的二进制数情况正好包括了这些选取状况).
for (int i = 1; i < 1 << m; i ++ )
// i<1<<m 组合数 2^m-1
{
int t = 1, s = 0;
for (int j = 0; j < m; j ++ )//遍历二进制的每一位
if (i >> j & 1)//判断二进制第j位是否存在
{
if ((LL)t * p[j] > n)
{
t = -1;
break;
}
t *= p[j];
s ++ ;
}
if (t != -1)
{
if (s % 2) res += n / t;
else res -= n / t;
}
}
C++ 代码
#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 ++ )
{
int t = 1, s = 0;
for (int j = 0; j < m; j ++ )
if (i >> j & 1)
{
if ((LL)t * p[j] > n)
{
t = -1;
break;
}
t *= p[j];
s ++ ;
}
if (t != -1)
{
if (s % 2) res += n / t;
else res -= n / t;
}
}
cout << res << endl;
return 0;
}
中于明白 了谢谢大佬
大佬,我想问一下,把i看做是1-(2^m-1)和位运算 是怎么考虑的啊,为什么i的第k位是1时,就能代表质因子为p[j]的情况?
位运算中二进制的每一位都和 每一个因子相对应吗,因子为p1、p2~pn、p1*p2等的情况?好难理解啊
呃呃呃,这个方法y总好像在其他视频里详细讲过
1<<m -1 转换为二进制就是111……(m个1) 当第 j 位是1时,就代表 p[j] 被选上,反之亦然。
因为二进制数每一位是否为1 与m个质数中每一个是否要选的方案的个数都是2^m-1次(不能都不选)
不太懂这段代码
可以带一些 数据进去,就好理解了
(LL)t * p[j] > n,那结果已经是 0,为了防止 t 过大,提前 break 掉,如果if 不成立,则累乘p[j],同时 s 表示目前有几个 1