容斥原理总结

容斥原理总结

概述:

先引入百度百科的定义:

在计数时,必须注意没有重复,没有遗漏。为了使重叠部分不被重复计算,人们研究出一种新的计数方法,这种方法的基本思想是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理。

推荐博客:Math-组合学】容斥原理的拓展以及乱序排列问题

一般可以描述如下:

要计算几个集合并集的大小,我们要先将所有单个集合的大小计算出来,然后减去所有两个集合相交的部分,再加回所有三个集合相交的部分,再减去所有四个集合相交的部分,依此类推,一直计算到所有集合相交的部分。

用韦恩图来表示:

上图就可以表示为:|A∪B∪C| = |A|+|B|+|C| – |A∩B| – |B∩C| – |C∩A| + |A∩B∩C|

例如:

给你一个数$n$,问从1~n中与$n$互质的数有多少个。

假设$n=30$,我们可以先求出30的质因数,30的质因数为:2,3,5

那么我们就可以看成是3个集合,集合中的元素分别为2,3,5,全集就为从1~30中的所有数

所以我们就从中减去2的倍数,3的倍数,5的倍数,但是6既是2的倍数也是3的倍数,被多算了一次,所以要减去6的倍数,同理减去$25$的倍数,$35$的倍数,最后加上$233}+\frac{30}{25}+\frac{30}{35}-\frac{30}{23*5}=8
$$
所以在1~30中与30互质的数有8个.

这个问题实际上也正是欧拉函数解决的问题,请看欧拉函数

模板

例题

  1. HDU1286 找新朋友(容斥原理+欧拉函数)

    这就是上面讲的那个题意了,给你一个数$n$,问从1~n中与$n$互质的数有多少个。

  1. HDU1695 GCD(容斥原理)

    题目给出了$a,b,c,d,k$,求有多少对$(x,y)$($x∈[a,b],y∈[c,d]$),满足$gcd(x,y)==k$,后台数据保证了$a$和$c$的值都为1,所以题目转化成求:从$[1,b]$中和$[1,d]$中满足$gcd(x,y)==k$的$(x,y)$的对数。

    那么题目就可进一步转化为求从$[1,\frac{b}{k}]​$和$[1,\frac{d}{k}]​$中有多少对$(x,y)​$满足$gcd(x,y)==1​$(互质)的对数。

    为了方便计算,我们在输入的时候进行处理,使得b<=d,那么$\frac{b}{k}<=\frac{d}{k}$,我们只需要从$[1,\frac{d}{k}]$中枚举$i$,找到在$[1,\frac{b}{k}]$中与$i$互质的数的个数:

    1. 当$i<=\frac{b}{k}$时枚举的数会重复,所以要去重$ans=\frac{ans+1}{2}$
    2. 当$i>\frac{b}{k}$时直接利用容斥原理枚举,最后两次枚举的和就是答案

  2. HDU2841 Visible Trees(容斥原理,二维)

题目转化一下就可以变成:已知x∈[1,n],y∈[1,m]求x和y这两个集合中互质的数的个数。利用容斥,枚举x集合,然后暴力加起来

  1. HDU4135 Co-prime(容斥原理)

题目给出了一个区间[a,b]和一个数n,让你求出a~b中与n互质的数的个数,我们只需要求出从1~b与n互质的数的个数减去1~a中与n互质的数的个数

  1. NYOJ762+POJ1796 第k个互质数(容斥原理+二分)

首先我们可以利用容斥原理知道:1~m(m为任意值)中与n互质的数的个数

然后考虑利用二分查找数字,然后判断这个数字和n有多少个互质数

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注