容斥原理
$|S_1 \cup S_2 \cup S_3| = |S_1| + |S_2| + |S_3| - |S_1 \cap S_2| - |S_1 \cap S_3| - |S_2 \cap S_3| + |S_1 \cap S_2 \cap S_3|$
项的个数
$(C_n^0) + C_n^1 + C_n^3 +…+C_n^n = 2^{n} - 1$
左边 = 每项取出$1$个集合的个数+取出$2$个集合的个数+…+取出$3$个集合 的总情况
右边 = 每个集合有两种状态,选或不选 的总情况
容斥原理的证明
设一个数$x$,出现在$k$个集合中, $1 <= k <= n$
则根据容斥原理: $x$被计算的次数:
$T = C_k^1 - C_k^2 + C_k^3 - C_k^4 +…+ (-1)^{k-1}C_k^k$
我们可以知道:$(1-x)^k = C_k^0 - C_k^1x + C_k^2x^{2}-C_k^3x^{3}+…+(-1)^{k}C_k^kx^k$
令$x = 1$, 则$(1-1)^k$ = $1-C_k^1+C_k^2-C_k^3+…+C_k^k$
因此移项可知:$T = 1$
$T = 1$代表$x$出现在各个集合中,只会被计算$1$次
得证;
题目思路
集合的表示
$S_i$代表第$i$个质数代表的集合, 即集合中的数都能被$p[i]$整除
(比如$p[i]=2$, 则$S_i$集合包含 被$2$整除的所有数)
项的内部计算
计算$|S_i|$ , $|S_i|$ 包含所有能被$p[i]$整除的数, 则可通过$s = \frac{n}{p_i}$,s
就是在$[1,n]$中被$p[i]$整除的数的个数
计算$|S_i \cap S_j|$, 它们的交集含义是既能被$p[i]$,又能被$p[j]$整除, 可通过$s = \frac{n}{p_i * p_j}$,s
就是在$[1,n]$中被$p[i]*p[j]$整除的数的个数
(其他集合计算类似)
如何得到每个项
二进制枚举法
for(int i = 1; i < 1 << m; i ++){
for(int j = 0; j < m; j ++)
if(i >> j & 1)
...
}
比如$01001$,$1$代表选该质数; 可知这样枚举达到每个项 都是不重不漏的
时间复杂度
质数的个数为$m$, 总共有$2^m$项集合计算, 而每个集合内部计算最大需要$m$次, 所以时间复杂度为$O(2^m*m)$
代码
#include<iostream>
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];
LL res = 0;
for(int i = 1; i < 1 << m; i ++){
LL t = 1, cnt = 0;
for(int j = 0; j < m; j ++)
if(i >> j & 1){
//不可能的情况, 直接退出
if((LL)t * p[j] > n){
t = -1;
break;
}
t *= p[j];
cnt ++;
}
if(t != -1){
//容斥原理的实现, 奇数加, 偶数减
if(cnt % 2) res += n / t;
else res -= n / t;
}
}
cout << res << endl;
return 0;
}