HDU-1796 How many integers can you find(容斥原理)

水深无声 2022-06-10 13:25 173阅读 0赞

##                     [How many integers can you find][]  Now you get a number N, and a M-integers set, you should find out how many integers which are small than N, that they can divided exactly by any integers in the set. For example, N=12, and M-integer set is \{2,3\}, so there is another set \{2,3,4,6,8,9,10\}, all the integers of the set can be divided exactly by 2 or 3. As a result, you just output the number 7.  Input    There are a lot of cases. For each case, the first line contains two integers N and M. The follow line contains the M integers, and all of them are different from each other. 0<N<2^31,0<M<=10, and the M integer are non-negative and won’t exceed 20.  Output    For each case, output the number.  Sample Input  12 2 2 3  Sample Output  7       题意：给一个数N，和一个集合M，问小于N的数中有多少个数可以被集合中的任意一个数整除。 ##

思路：这就是一个简单的容斥原理入门题，用位运算表示集合M中的各个数是选还是不选，然后加奇减偶，然后还要特判一下0的情况。

#include<iostream>  
    #include<cstring>  
    #include<string>  
    #include<cmath>  
    #include<cstdio>  
    using namespace std;
    __int64 sum;
    int n, m;
    int a[25];
    int b[25];
    int visi[25];
    
    __int64 gcd(__int64 m, __int64 n)
    {
    	__int64 tmp;
    	while (n)
    	{
    		tmp = m%n;
    		m = n;
    		n = tmp;
    	}
    	return m;
    }
    
    __int64 lcm(__int64 m, __int64 n)
    {
    	return m / gcd(m, n)*n;
    }
    
    void cal()
    {
    	int flag = 0, i;
    	__int64 t = 1;
    	__int64 ans;
    	for (i = 0; i<m; i++)
    	{
    		if (visi[i])
    		{
    			flag++;   //记录用了多少个数  
    			t = lcm(t, b[i]);
    		}
    	}
    	ans = n / t;
    	if (n%t == 0) ans--;
    	if (flag & 1) sum += ans;   //加奇减偶  
    	else sum -= ans;
    }
    
    int main()
    {
    	int i, j, p;
    	while (~scanf("%d%d", &n, &m))
    	{
    		sum = 0;
    		for (i = 0; i<m; i++)
    			scanf("%d", &a[i]);
    
    		int tt = 0;  //  
    		for (i = 0; i<m; i++)
    		{
    			if (a[i])  //去掉0  
    				b[tt++] = a[i];
    		}
    		m = tt;
    		p = 1 << m;   //p表示选取多少个数，组合数的状态  
    		for (i = 1; i<p; i++)
    		{
    			int tmp = i;
    			for (j = 0; j<m; j++)
    			{
    				visi[j] = tmp & 1;
    				tmp >>= 1;
    			}
    			cal();
    		}
    		printf("%I64d\n", sum);
    	}
    	return 0;
    }

[How many integers can you find]: https://vjudge.net/problem/HDU-1796