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/tif (s % 2) res += n / t;else res -= n / t;}}// 输出结果cout << res << endl;return 0;
}