容斥定理以及其应用

下面仅仅是我在学习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
递归计算代码如下：

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即是跟素因子相关的数的个数
}

最后

以上就是爱撒娇康乃馨为你收集整理的容斥定理以及其应用的全部内容，希望文章能够帮你解决容斥定理以及其应用所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。