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

• 一、容斥原理
• • 1、定理内容
• 二、代码模板
• • 1、问题
  • • （1）如何求出能够被整除的个数？
    • （2）如何枚举出2n−12^n-12n−1种情况？
  • 2、代码实现：

一、容斥原理

1、定理内容

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

我们看下面的图：

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

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

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

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

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

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

我们可以看作我们的前面有nnn个集合SSS，那么我们从中选出1个集合就是Cn1C_n^1Cn1​。
选出任意两个集合的交集，就是Cn2C_n^2Cn2​

那么依次类推：

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

Cn1+Cn2+Cn3+...+CnnC_n^1+C_n^2+C_n^3+...+C_n^nCn1​+Cn2​+Cn3​+...+Cnn​

而根据我们高中的知识：
Cn0+Cn1+Cn2+Cn3+...+Cnn=2nC_n^0+C_n^1+C_n^2+C_n^3+...+C_n^n=2^nCn0​+Cn1​+Cn2​+Cn3​+...+Cnn​=2n

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

Cn1+Cn2+Cn3+...+Cnn=2n−1C_n^1+C_n^2+C_n^3+...+C_n^n=2^n-1Cn1​+Cn2​+Cn3​+...+Cnn​=2n−1

时间复杂度就是O(2n)O(2^n)O(2n)

二、代码模板

1、问题

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

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

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

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

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

其实很简单，能被p1p_1p1​整除的个数是[Np1][\frac{N}{p_1}][p1​N​]，

中间的交集的话，我们以能够被p1p_1p1​或者p2p_2p2​为例。我们只需要求[Np1∗p2][\frac{N}{p_1*p_2}][p1​∗p2​N​]

依次类推。

（2）如何枚举出2n−12^n-12n−1种情况？

那么这个枚举的话，可以采用二进制的思想，我们的情况一共是2n−12^n-12n−1种，我们将其转化为二进制的话，（以n=3）为例：

23−1=1112^3-1=11123−1=111

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

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

而我们的所有情况无非就是从001−111001-111001−111，换算为十进制的话，我们就是要枚举从111到2n−12^n-12n−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//t用来记录结果，s用来记录集合的个数int t=1,s=0;//枚举情况i的二进制位for(int j=0;jif(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<