第三十六章数论——容斥原理原创

原标题：第三十六章 数论——容斥原理
原创

1、定理内容

我们在高中阶段都学过韦恩图，韦恩图其实就是用来描述集合与集合之间的关系的。

我们看下面的图：

这道题的话，我们首先将三个圆圈加在一起，但是叶子形状的部分会被我们重复加了两遍，所以我们要减去。但是三个叶子形状的中间也会有交叉的部分。所以这个部分又被我们减少了三次。所以我们还要再加上一次中间部分。

因此，就出现了我们图中的红色式子。

因此，我们总结出了一个规律。如果我们求的是奇数个集合的合并，那么我们就要加上。如果是偶数个集合的合并，我们就要减去。

那么我们从这个特殊的例子推广到一般情况，就会得到如下公式：

而这个式子就是我们的容斥原理。

那么容斥原理的时间复杂度是多少呢？

我们可以看作我们的前面有$n$个集合$S$，那么我们从中选出1个集合就是





C


n


1




C_n^1


Cn1​。
选出任意两个集合的交集，就是





C


n


2




C_n^2


Cn2​

那么依次类推：

我们选出所有集合所需的情况就是：

C


n


1



+



C


n


2



+



C


n


3



+


.


.
文章来源地址10912.html

.


+



C


n


n




C_n^1+C_n^2+C_n^3+...+C_n^n


Cn1​+Cn2​+Cn3​+...+Cnn​

而根据我们高中的知识：






C


n


0



+



C


n


1



+



C


n


2



+



C


n


3



+


.


.


.


+



C


n


n



=



2


n




C_n^0+C_n^1+C_n^2+C_n^3+...+C_n^n=2^n


Cn0​+Cn1​+Cn2​+Cn3​+...+Cnn​=2n

那么我们选出所有情况来运用容斥原理计算的次数就是：

C


n


1



+



C


n


2



+



C
文章来源站点https://www.yii666.com/

n


3



+


.


.


.


+

www.yii666.com

C


n


n



=



2


n



−


1



C_n^1+C_n^2+C_n^3+...+C_n^n=2^n-1


Cn1​+Cn2​+Cn3​+...+Cnn​=2n−1

时间复杂度就是




O


(



2


n



)



O(2^n)


O(2n)

1、问题

这道题可以转化成下面的图片：

紫色圈代表能够被p1整除的，绿色圈代表能被p2整除的，依此类推。题目中就是让我求上图中的元素个数。

如果我们只是单纯的把被某个数整除的数字个数加起来的话，中间一定会有重复的。因此，我们需要根据容斥原理来求。

利用容斥原理的话，我们有以下几个问题：

（1）如何求出能够被整除的个数？

其实很简单，能被





p


1




p_1


p1​整除的个数是




[



N



p


1




]



[\frac{N}{p_1}]


[p1​N​]，

中间的交集的话，我们以能够被





p


1




p_1


p1​或者





p


2




p_2


p2​为例。我们只需要求




[



N




p


1



∗



p


2





]



[\frac{N}{p_1*p_2}]


[p1​∗p2​N​]

依次类推。

（2）如何枚举出





2


n



−


1



2^n-1


2n−1种情况？

那么这个枚举的话，可以采用二进制的思想，我们的情况一共是





2


n



−


1



2^n-1


2n−1种，我们将其转化为二进制的话，（以n=3）为例：

2


3



文章来源地址10912.html www.yii666.com −


1


=


111



2^3-1=111


23−1=111

每一位代表一个集合，此时三位都是1，说明我们要求三个集合的交集。

那么如果是$101$，就代表我们要求第一个集合和第三个集合的交集。

而我们的所有情况无非就是从$001-111$，换算为十进制的话，我们就是要枚举从$1$到





2


n



−


1



2^n-1


2n−1。这中间的每个数字的二进制位都代表着一种情况。

当上述两个问题解决之后，我们就可以套用容斥原理的公式了。

2、代码实现：

#include
using namespace std;
typedef long long LL;
const int N=20;
int p[N];
int main()
{
int n,m,res=0;
cin>>n>>m;
//读取除数
for(int i=0;i<m;i++)scanf("%d",p+i);
//枚举情况
for(int i=1;i<1<<m;i++)
{
//t用来记录结果，s用来记录集合的个数
int t=1,s=0;
//枚举情况i的二进制位
for(int j=0;j<m;j++)
{
if(i>>j&1)//如果这一位是1，那么就让该位对应的集合参与运算
{
if((LL)t*p[j]>n)//如果几个数的积，已经大于了n，那么这种情况不存在。
{
t=0;//如果不存在了，就直接扔掉就好了。
break;
}
t*=p[j];//乘上该集合所对的除数
s++;//记录参与的集合个数
}
}
if(t)
{
//使用容斥原理：
if(s%2)res+=n/t;//如果集合是奇数就加上
else res-=n/t;//如果集合是偶数就减去
}
}
cout<<res<<endl;
}


来源于：第三十六章 数论——容斥原理
原创