76题能被整除的数有哪些？
摘要：76.Acwing基础课第890题-简单-能被整除的数 题目描述 (给定一个整数 n 和 m 个不同的质数 p_1,p_2,…,p_m)。 (请你求出 1∼n 中能被 p_1,p_2,…,p_m 中的至少一个数整除的整数有多少个)。
76.Acwing基础课第890题-简单-能被整除的数
题目描述
\(给定一个整数 n 和 m 个不同的质数 p_1,p_2,…,p_m\)。
\(请你求出 1∼n 中能被 p_1,p_2,…,p_m 中的至少一个数整除的整数有多少个\)。
输入格式
\(第一行包含整数 n 和 m\)。
\(第二行包含 m 个质数\)。
输出格式
\(输出一个整数，表示满足条件的整数的个数\)。
数据范围
\(1≤m≤16\),
\(1≤n,p_i≤10^9\)
输入样例：
10 2
2 3
输出样例：
7
代码：
// 包含基础输入输出、算法头文件
#include <iostream>
#include <algorithm>
using namespace std;
// 定义长整型别名：防止乘法溢出（如多个质数相乘可能超过int范围）
typedef long long LL;
// 常量定义：N=20，最多支持20个质数（2^20≈1e6，循环次数可接受）
const int N = 20;
int p[N]; // 存储输入的m个质数
int main()
{
int n, m; // n：范围上限（1~n）；m：质数的个数
cin >> n >> m;
// 输入m个质数，存入p数组
for (int i = 0; i < m; i ++ ) cin >> p[i];
int res = 0; // 最终结果：1~n中能被至少一个质数整除的数的个数
// ========== 核心：二进制枚举所有非空子集（容斥原理） ==========
// 1<<m 表示2^m（所有子集的数量），i从1开始枚举非空子集
for (int i = 1; i < 1 << m; i ++ )
{
int t = 1; // 存储当前子集所有质数的乘积
int s = 0; // 存储当前子集的元素个数（质数个数）
// 遍历当前子集的每一位，判断是否包含第j个质数
for (int j = 0; j < m; j ++ )
// i >> j & 1：判断i的第j位是否为1（包含第j个质数）
if (i >> j & 1)
{
// 防溢出：如果当前乘积*t超过n，后续n/t=0，无需计算
if ((LL)t * p[j] > n)
{
t = -1; // 标记溢出，跳出循环
break;
}
t *= p[j]; // 累乘当前质数
s ++ ; // 子集大小+1
}
// 如果乘积未溢出（有效子集）
if (t != -1)
{
// 容斥原理：奇加偶减
// 子集大小为奇数：加上n/t（1~n中能被t整除的数的个数）
// 子集大小为偶数：减去n/t
if (s % 2) res += n / t;
else res -= n / t;
}
}
// 输出结果
cout << res << endl;
return 0;
}