第 36 章 数论--公差原理

一、容斥原理

1、定理内容

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

我们看下面的图：

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

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

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

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

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

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

我们可以看作我们的前面有$n$个集合$S$，那么我们从中选出1个集合就是$C_n^1$。
选出任意两个集合的交集，就是$C_n^2$

那么依次类推：

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

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

而根据我们高中的知识：
$$C_n^0+C_n^1+C_n^2+C_n^3+...+C_n^n=2^n$$

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

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

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

二、代码模板

1、问题

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

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

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

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

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

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

中间的交集的话，我们以能够被$p_1$或者$p_2$为例。我们只需要求$[\frac{N}{p_1\ast p_2}]$

依次类推。

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

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

$2^3-1=111$

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

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

而我们的所有情况无非就是从$001-111$，换算为十进制的话，我们就是要枚举从$1$到$2^n-1$。这中间的每个数字的二进制位都代表着一种情况。

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

2、代码实现：

#include<iostream>
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;
}