AcWing 890：能被整除的数 ← 容斥原理
【题目来源】
https://www.acwing.com/problem/content/892/
【题目描述】
给定一个整数 n 和 m 个不同的质数 p1，p2，...，pm。
请你求出 1~n 中能被 p1，p2，...，pm 中的至少一个数整除的整数有多少个。
【输入格式】
第一行包含整数 n 和 m。
第二行包含 m 个质数。
【输出格式】
输出一个整数，表示满足条件的整数的个数。
【输入样例】
10 2
2 3
【输出样例】
7
【数据范围】
1≤m≤16，
1≤ni, pi≤10^9
【算法分析】
● 容斥原理，是解决「多集合并集大小」问题的核心数学方法。
设 S 为集合 {A1,A2,…,Am} 的任意非空子集，|S| 表示子集的元素个数，则：
|A1 U A2| = |A1| + |A2| - |A1 ∩ A2|
|A1 U A2 U A3| = |A1| + |A2| + |A3| - |A1 ∩ A2| - |A1 ∩ A3| - |A2 ∩ A3| + |A1 ∩ A2 ∩ A3|
|A1 U A2 U A3 U A4| = |A1| + |A2| + |A3| + |A4|
- |A1 ∩ A2| - |A1 ∩ A3| - |A1 ∩ A4| - |A2 ∩ A3| - |A2 ∩ A4| - |A3 ∩ A4|
+ |A1 ∩ A2 ∩ A3| + |A1 ∩ A2 ∩ A4| + |A1 ∩ A3 ∩ A4| + |A2 ∩ A3 ∩ A4|
- |A1 ∩ A2 ∩A3 ∩ A4|
其他，以此规律类推。
● 容斥原理求解的二进制思想
在容斥原理中，二进制思想是实现子集枚举的核心手段，也是竞赛中高效实现容斥的标准方法。其核心逻辑是：用二进制数的每一位表示对应集合是否被选中，通过遍历所有非空二进制数，等价遍历容斥所需的所有非空子集，再结合二进制位的统计（1 的个数）确定容斥的符号和计算逻辑。
这种方法把抽象的子集选择问题转化为具体的二进制数遍历问题，无需复杂的递归 / 回溯，仅通过循环即可实现，代码简洁、效率高（时间复杂度为 O(m*2^m)，m 为集合个数，竞赛中 m 一般不超过 20，20*(2^20)≈2*1e7 完全可接受）。
● 容斥原理中 “能被整除的数的个数” 的核心逻辑可概括为如下两个原理
原理 1：1~n 中能被 k 整除的数是 k,2k,3k,...,mk，其中 mk≤n，因此最大的 m 就是 ⌊n/k⌋，这个 m 就是符合条件的数的个数。
例如，求 1~20 中能被 3 整除的数的个数 → ⌊20/3⌋=6（3、6、9、12、15、18），结果正确。
原理 2：一个数能同时被 k1,k2,...,km 整除，当且仅当它能被这几个数的最小公倍数整除。若 k1,k2,...,km 两两互质，则 LCM(k1,k2,...,km)=k1×k2×...×km。
例子 1（两两互质）：求 1~20 中能同时被 2、3 整除的数的个数 → LCM (2,3)=6 → ⌊20/6⌋=3（6、12、18），正确。
例子 2（非互质）：求 1~20 中能同时被 4、6 整除的数的个数 → LCM (4,6)=12 → ⌊20/12⌋=1（12），若直接相乘 4×6=24，⌊20/24⌋=0，结果错误，因此非互质时必须求 LCM，不能直接相乘（竞赛高频坑点）。
● 为什么能用 m 个二进制位来对应 m 个数的组合选择？
（1）一个 m 位二进制数总共有 2^m 种可能（从 00...0 到 11...1）。排除全 0 的空组合，剩下的 2^m - 1 种组合刚好是所有非空组合，完全覆盖所需的非空组合情况。
（2）这其实是「二进制枚举组合」的经典技巧，本质是用二进制位的 “0/1” 状态，对应 “选 / 不选” 某个元素的决策。
● 核心代码解析
（1）代码的逻辑框架：枚举所有非空组合 → 计算组合乘积 → 按容斥规则更新结果。
（2）变量 p 及 cnt 的含义
p=1：表示当前组合中元素的乘积，即组合中各个 a[] 元素的乘积，初始化为 1。
cnt=0：表示当前组合的「元素个数」，即选中了多少个 a[] 元素，初始化为 0。
注意：这两个变量在「每次外层循环（每个组合）」都会重新初始化，保证每个组合的计算互不干扰。
（3）外层循环的 i 对应一个组合，内层循环的 j 遍历 a[] 的所有元素（第 j 个元素 a[j]）。
int ans=0;
for(int i=1; i<(1<>j)&1) {
if((LL)p*a[j]>n) {
p=-1;
break;
}
p*=a[j];
cnt++;
}
if(p!=-1) {
if(cnt%2) ans+=n/p;
else ans-=n/p;
}
}
cout< （4）溢出判断与无效乘积过滤：(LL)p*a[j]>n
☆ 为什么要强制转 LL？p 和 a[j] 都是 int 类型，它们的乘积可能超过 int 的取值范围（比如 int 最大约 2e9），先强制转换为 long long 再计算，避免溢出导致的错误判断。
☆ 为什么要判断 >n？如果当前组合的乘积已经超过 n，那么 1~n 中不可能有能被这个乘积整除的数（n/p 结果为 0），后续计算无意义，直接标记为无效。
☆ 标记无效：p=-1 是一个「哨兵值」，用来标记当前组合的乘积无效，后续不会参与 ans 的更新；break 跳出内层循环，无需继续计算当前组合的剩余元素。
（5）累乘更新乘积：p*=a[j]
只有当乘积有效（≤n）时，才将 a[j] 乘入 p，得到当前组合的累计乘积。
比如：选中 a[0]=2，p 从 1 变成 2；再选中 a[1]=3，p 从 2 变成 6。
（6）统计组合元素个数：cnt++
每选中一个有效的 a[j]，组合元素个数就加 1，为后续容斥原理的「加 / 减」判断做准备。
● 十进制数的二进制表示中 1 的个数：https://blog.csdn.net/hnjzsyjyj/article/details/155950508
#include
using namespace std;
int main() {
int x,cnt=0;
cin>>x;
while(x) {
if(x&1) cnt++;
x>>=1;
}
cout< 【算法代码】
#include
using namespace std;
typedef long long LL;
const int N=20;
int a[N];
int main() {
int n,m;
cin>>n>>m;
for(int i=0; i>a[i];
int ans=0;
for(int i=1; i<(1<>j)&1) {
if((LL)p*a[j]>n) {
p=-1;
break;
}
p*=a[j];
cnt++;
}
}
if(p!=-1) {
if(cnt%2) ans+=n/p;
else ans-=n/p;
}
}
cout<
【参考文献】
https://www.acwing.com/solution/content/29702/
https://www.cnblogs.com/vanhopex/p/15967186.html
https://mp.weixin.qq.com/s/o36FMXYm4a7z5ieUdUyw7Q
