UVA 10325 The Lottery （组合数学，容斥原理，二进制枚举）

男娘i 2022-07-26 05:17 166阅读 0赞

UVA 10325 The Lottery （组合数学，容斥原理，二进制枚举）：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=111598\#problem/A][http_acm.hust.edu.cn_vjudge_contest_view.action_cid_111598_problem_A] 传送门：nefu

题面描述：

The Sports Association of Bangladesh is in great problem with their latest lottery 'Jodi laiga Jai'. There are so many participants this time that they cannot manage all the numbers. In an urgent meeting they have decided that they will ignore some numbers. But how they will choose those unlucky numbers!! Mr. NondoDulal who is very interested about historic problems proposed a scheme to get free from this problem.

You may be interested to know how he has got this scheme. Recently he has read the Joseph's problem.

## The Problem ##

There are N tickets which are numbered from 1 to N. Mr. Nondo will choose M random numbers and then he will select those numbers which is divisible by at least one of those M numbers. The numbers which are not divisible by any of those M numbers will be considered for the lottery.

As you know each number is divisible by 1. So Mr. Nondo will never select 1 as one of those M numbers. Now given N,M and M random numbers, you have to find out the number of tickets which will be considered for the lottery.

The Input

Each input set starts with two Integers N (10<=N<2^31) and M (1<=M<=15). The next line will contain M positive integers each of which is not greater than N. Input is terminated by EOF.

## The Output ##

Just print in a line out of N tickets how many will be considered for the lottery.

Sample Input

10 2
    2 3
    20 2
    2 4

## Sample Output ##

3
    10

题目大意：

计算在1到N中不能被给定的M个数都不能整除的数的个数。

题目分析：

正常想的话，就是从1到N遍历，并判断每一个数是否能被给定的M个数整除，并要进行标记，把能整除的都标记下来（注意不要重复计算），之后再找一遍数组中没有被标记的数的个数即为所求，但是由于N比较大，并不能开出来如此大的数组，所以，此方法行不通。

换一种想法，由于只是让求满足条件的数的个数，所以没有必要把满足条件的数字都记录下来，而且不能整除不好想，我们就去想他的反面，看有多少个数能被给定的M个数整除，然后再用N去减即可。所以，我们可以考虑对于N个数中，能被M1整除的数有N/M1个，同样对于M2，能被M2整除的数有N/M2个，但是要是同时考虑M1和M2则会出现问题，因为，有既能被M1整除又能被M2整除的重复记录的数，所以我们考虑到了容斥原理，奇数加偶数减的去找这给定M个数的两两、三三、四四、……的最小公倍数即可。当然要借助于二进制枚举去进行数据的处理，具体代码实现如下：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    long long gcd(long long a,long long b)
    {
        if(b==0)
            return a;
        else
            return gcd(b,a%b);
    }
    
    long long lcm(long long a,long long b)
    {
        return a*b/gcd(a,b);
    }
    
    int main()
    {
        long long n,m;
        long long a[20];
        long long x[20];
        while(scanf("%lld%lld",&n,&m)!=EOF)
        {
            for(int i=0; i<m; i++)
            {
                scanf("%lld",&a[i]);
            }
            memset(x,0,sizeof(x));
            long long t,lcmm;
            for(long long i=1; i<(1<<m); i++)
            {
                t=i;
                lcmm=1;
                long long s=0,l,k=0;
                while(t!=0)
                {
                    l=t%2;
                    k++;
                    t=t/2;
                    if(l==1)
                    {
                        lcmm=lcm(lcmm,a[k-1]);
                        s++;
                    }
                }
                x[s-1]=x[s-1]+(n/lcmm);
            }
            long long ans=0;
            for(long long i=0; i<m; i++)
            {
                if(i%2==0)
                    ans+=x[i];
                else
                    ans-=x[i];
            }
            printf("%lld\n",n-ans);
        }
        return 0;
    }

[http_acm.hust.edu.cn_vjudge_contest_view.action_cid_111598_problem_A]: http://http://acm.hust.edu.cn/vjudge/contest/view.action?cid=111598#problem/A