【题目来源】
AcWing：890. 能被整除的数 - AcWing题库
【题目描述】
给定一个整数 \(n\) 和 \(m\) 个不同的质数 \(p_1,p_2,\dots,p_m\)。
请你求出 \(1\sim n\) 中能被 \(p_1,p_2,\dots,p_m\) 中的至少一个数整除的整数有多少个。
【输入】
第一行包含整数 \(n\) 和 \(m\)。
第二行包含 \(m\) 个质数。
【输出】
输出一个整数，表示满足条件的整数的个数。
【输入样例】
10 2
2 3
【输出样例】
7
【解题思路】
【算法标签】
《AcWing 890 能被整除的数》 #容斥原理#
【代码详解】
#include <bits/stdc++.h>
using namespace std;typedef long long LL; // 定义 LL 为 long long 类型
const int N = 20; // 定义常量 N，表示质数的最大数量
int p[N]; // p 数组存储质数
int n, m; // n 表示范围上限，m 表示质数的数量int main()
{cin >> n >> m; // 输入范围上限 n 和质数的数量 mfor (int i = 0; i < m; i++) cin >> p[i]; // 输入质数int ans = 0; // 初始化答案为 0for (int i = 1; i < 1 << m; i++) { // 遍历所有可能的质数组合（二进制枚举）int s = 0; // s 表示当前组合中质数的个数int t = 1; // t 表示当前组合中质数的乘积for (int j = 0; j < m; j++) { // 遍历每个质数if (i >> j & 1) { // 如果当前质数被选中if ((LL)t * p[j] > n) { // 如果乘积超过 nt = -1; // 标记为无效组合break; // 跳出循环} else {t = t * p[j]; // 更新乘积s++; // 增加质数个数}}}if (t != -1) { // 如果组合有效if (s % 2) ans = ans + n / t; // 如果质数个数为奇数，加上 n/telse ans = ans - n / t; // 如果质数个数为偶数，减去 n/t}}cout << ans << endl; // 输出答案return 0; // 程序结束
}
【运行结果】
10 2
2 3
7