ACM_容斥原理

容斥原理是在计数时，必须注意没有重复，没有遗漏。于是人们想出来的一种计数方法：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复。用两个集合来讲就是A∪B =|A∪B| = |A|+|B| - |A∩B |，如果是三个集合的话就是|A∪B∪C| = |A|+|B|+|C| - |A∩B| - |B∩C| - |C∩A| + |A∩B∩C|，不难发现，出现的元素是奇数就加，偶数就减，这个原理应该也比较好懂，n个元素就总共有2^n-1种取法，只要把这2^n-1种东西列出来，奇加偶减就可以解决。

容斥原理在计算互质的数的个数的时候应用的比较广泛，因为一个数可以分解成几个质因子，和它互质的数就是不拥有相同质因子的数，所以我们在某个区间中用容斥原理找到与它不互质的数的个数，再用全集去减即可得到答案。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
using namespace std;
typedef long long ll;
ll prime[70];
ll m,n;
void get_prime()
{
for(ll i=2;i*i<=n;i++)
if(n&&n%i==0) //对n进行素因数分解
{
prime[m++]=i;
while(n&&n%i==0) n/=i;
}
if(n>1) prime[m++]=n;
}
ll solve(ll num)
{
ll i,j;
ll ans=0,tem,flag;
for(i=1;i<1<<m;i++)
{
tem=1,flag=0;
for(j=0;j<m;j++)
if(i&1<<j)
flag++,tem*=prime[j];
if(flag&1) ans += num/tem; //容斥原理，奇加偶减
else ans -= num/tem;
}
return ans;
}
int main()
{
int t;
ll a,b,k=1;
scanf("%d",&t);
while(t--)
{
m=0;
scanf("%lld%lld%lld",&a,&b,&n);
get_prime();
printf("%lldn",b-solve(b)-(a-1-solve(a-1)));
}
return 0;
}

最后

以上就是玩命月饼为你收集整理的ACM_容斥原理的全部内容，希望文章能够帮你解决ACM_容斥原理所遇到的程序开发问题。

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