容斥原理
- 内容
用于解决多个有相交情况的集合的并集，例如三个集合的情形：
对于n个集合的交集有公式:\(|S_1\cup S_2\cup S_3\cup \dots S_n|=(|S_1|+|S_2|+|S_3|+\dots+|S_n|)-(|S_1\cap S_2|+|S_1\cap S_3|+\dots+|S_{n-1}\cap S_{n}|+(|S_1\cap S_2 \cap S_3|+|S_1\cap S_2\cap S_4|+\dots+|S_{n-2}\cap S_{n-1} \cap S_{n}|\dots+{(-1)}^{n-1}(|S_1\cap S_2 \cap S_3\dots \cap S_n)|)\)
即：奇数个集合相交前面的系数为正，偶数个集合相交系数为负。
- 数学证明
若证：\(|S_1\cup S_2\cup S_3\cup \dots S_n|=(|S_1|+|S_2|+|S_3|+\dots+|S_n|)-(|S_1\cap S_2|+|S_1\cap S_3|+\dots+|S_{n-1}\cap S_{n}|+(|S_1\cap S_2 \cap S_3|+|S_1\cap S_2\cap S_4|+\dots+|S_{n-2}\cap S_{n-1} \cap S_{n}|\dots+{(-1)}^{n-1}(|S_1\cap S_2 \cap S_3\dots \cap S_n)|)\)
只需证：对于任意一个其中的元素x，其属于n个集合中的k个，都有:\(C_k^1-C_k^2+\dots+(-1)^{k-1}C_k^k=1\)即可,我们发现对于\((1-1)^{k}\)二项式展开有：\((-1+1)^{k}=1-C_k^1+C_k^2-C_k^3+\dots+(-1)^kC_k^k\Longleftrightarrow0=1-C_k^1+C_k^2-C_k^3+\dots+(-1)^kC_k^k\Longleftrightarrow C_k^1-C_k^2+\dots+(-1)^{k-1}C_k^k=1\),证毕。 - 代码实现
给定一个n和m个不同的质数\(P_1,P_2,P_3\dots P_m\)，求出1-n中至少能被一个P整除的数有多少个。
#include<iostream>
using namespace std;
typedef long long LL;
const int M=20;
int p[M];
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++)
{
int x;
scanf("%d",&x);
p[i]=x;
}
int res=0;
for(int i=1;i<1<<m;i++)//将所有质数选择情况用1-(2^m-1)的二进制数这2^m-1种情况表示,其中1代表选了这个质数,0表示没选
{
int 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;
}
}
}
printf("%d\n",res);
return 0;
}
- 代码思路及细节
由数学知识显然有：1-n中能被\(P_i\)整除的数有\(\lfloor \frac{n}{P_i} \rfloor\)个，且1-n中能被\(P_i和P_k\)同时整除的数有\(\lfloor \frac{n}{P_i*P_k} \rfloor\)个，以此类推：1-n中能被\(P_1P_2\dots P_m\)整除的数有\(\lfloor \frac{n}{P_1P_2\dots P_m} \rfloor\)个。
对于质数选择的表示我们用了一个小技巧，就是用\(1到2^{m-1}\)这\(2^{m-1}\)个数的二进制来表示，1表示选了这个质数，0代表没有选，例如101就表示选了第一个和第三个质数来求它们在1~n至少能被其中一个数整除的数有多少个。