Hdu 1796 How many integers can you find (容斥原理递归及循环的一般写法)

朱雀 2022-08-26 04:55 139阅读 0赞

题意：给出n和由m个元素的集合，求小于n且是集合中任意元素的倍数的数有多少个。

把集合中的0先去掉。

#include <cstdio>
    
    int data[20],n,m,cnt;
    __int64 sum;
    
    __int64 Gcd (__int64 x,__int64 y)
    {
    	return y==0?x:Gcd(y,x%y);
    }
    
    void dfs (int now, int sym, __int64 lcm)
    {
    	lcm=data[now]/Gcd(lcm,data[now])*lcm;
    	sum+=n/lcm*sym;
    	for (int i=now+1;i<m;i++)
    		dfs(i,-sym, lcm);
    }
    
    int main ()
    {
    	while (~scanf("%d%d", &n, &m))
    	{
    		int i;
    		cnt=0;
    		n--;
    		for (i=0;i<m;i++)
    		{
    			int tmp;
    			scanf("%d",&tmp);
    			if (tmp)
    				data[cnt++]=tmp;
    		}
    		m=cnt;
    		sum=0;
    		for (i=0;i<m;i++)
    			dfs(i,1,data[i]);
    		printf("%I64d\n",sum);
    	}
    	return 0 ;
    }

#include <cstdio>
    #include <cstring>
    
    __int64 Gcd (__int64 x,__int64 y)
    {
    	return y==0?x:Gcd(y,x%y);
    }
    
    __int64 Lcm (__int64 x,__int64 y)
    {
    	return x*y/Gcd(x,y);
    }
    
    int main ()
    {
    	int n,m,data[15],i;
    	while (~scanf("%d%d",&n,&m))
    	{
    		if (m==0)
    		{
    			printf("0\n");
    			continue;
    		}
    		int cnt=0;
    		for (i=0;i<m;i++)
    		{
    			int tmp;
    			scanf("%d",&tmp);
    			if (tmp>0)
    			data[cnt++]=tmp;
    		}
    		n--;
    		__int64 s=0;
    		for (i=1;i<(1<<m);i++)
    		{
    			__int64 l=1,sum=0;
    			for (int j=0;j<m;j++)
    			{
    				if ((i>>j)%2==1) //取某一位
    				{
    					sum++;
    					l=Lcm(l,data[j]);
    				}
    			}
    			if (sum%2==0) //偶数个集合间的运算
    				s-=n/l;
    			else s+=n/l;
    		}
    		printf("%I64d\n",s);
    	}
    	return 0;
    }