题解 | #集合中的质数#

题目描述

给出一个集合和一个数m。

集合里面有n个质数。

请你求出从 1 到 m 的所有数中，至少能被集合中的一个数整除的数的个数。

思路

容斥原理： 先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复。

1-m的数中，

对于数x -> 存在m/x个

对于数x,y -> 存在m/x/y个

对于数x,y,z -> 存在m/x/y/z个

如果数有奇数个 就加上

如果数有偶数个 就减去

if(num&1) ans+=x;
else ans-=x;

枚举子集

对于n个数，有(1<<n)-1个非空子集

for(int i=1;i<(1<<n);i++)
{
  int x=m,num=0;
  for(int j=0;j<n;j++)
  {
    if(i&(1<<j)) 
    {
      num++;
      x/=prime[j];
    }
  }
  if(num&1) ans+=x;
  else ans-=x;
}

AC代码

#include<bits/stdc++.h>
using namespace std;
 
int n,m;
int prime[21];

int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
		cin>>prime[i];
	int ans=0;
	for(int i=1;i<(1<<n);i++)
	{
		int x=m,num=0;
		for(int j=0;j<n;j++)
		{
			if(i&(1<<j)) 
			{
				num++;
				x/=prime[j];
			}
		}
		if(num&1) ans+=x;
		else ans-=x;
	}
	printf("%d\n",ans);
	return 0;
}