容斥定理以及其应用

104 阅读 0 评论 69 点赞

我是靠谱客的博主爱撒娇康乃馨，这篇文章主要介绍容斥定理以及其应用，现在分享给大家，希望可以做个参考。

下面仅仅是我在学习ACM中所遇到的应用场景，如果以后有遇到再另行补充

这里写图片描述
举个栗子：

以51nod 上的一道题说一下，题目意思是求解10以内不能被2 3 5 7整除的数的个数。
利用容斥定理，计算出能被2 3 5 7 整除的数的个数即：
ans=n/2+n/3+n/5+n/7−n/6−n/10−n/14−n/15−n/21−n/35+n/30+n/42+n/70+n/105−n/210; a n s = n / 2 + n / 3 + n / 5 + n / 7 − n / 6 − n / 10 − n / 14 − n / 15 − n / 21 − n / 35 + n / 30 + n / 42 + n / 70 + n / 105 − n / 210 ;
然后用10减去ans就是最终答案。
①计算小于等于b的数中有多少跟b互素。
这也很明显可以用欧拉函数进行计算并且方便快解。
但如果得用每次计算的值呢，欧拉就不适用了，就比如POJ 1091需要计算一个序列不能有公因子。此时拿容斥就很好的解决了，计算出所有有公因子的，然后总数相减就是结果。
还可以计算小于等于a的数中跟b的所有素因子互质的数的个数。如HDU 1695
递归计算代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void dfs(int i,int nu,int x,int mu){
///数组下标，当前已经计算了的因子数，目前一共能够计算的因子数（传进来的），因子的乘积
if(nu==x){
sum+=b/mu;
//b是上文所说的小于等于的那个数
return ;
}if(i==cnt) return ;
dfs(i+1,nu+1,x,mu*p[i]);
//p数组存放的即为素因子
dfs(i+1,nu,x,mu);
}
int main()
{
fac();
//计算所有的素因子
ll ans = 0;
for (int i = 1; i <= cnt; i++)
//cnt即素因子的个数
{
sum = 0;
dfs(0,0,i,1);
if(i & 1)ans += sum;
else ans -= sum;
}
//计算出的ans即是跟素因子相关的数的个数
}