UVA OJ P10325 The Lottery

2019-08-02

这题主要是对容斥原理的考察

The Lottery

Problem Description

        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.
        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 ﬁnd out the number of tickets which will be considered for the lottery.

Input

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

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

这题的思路比较简单，直接暴力枚举容易错还容易超时，直接用容斥定理可以轻松解决

代码如下：

/*-------------------------
 *@Author:   ChenShou     |
 *@Language: C++          |
---------------------------*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>

//#define DEBUG
#define RI register int
#define endl "\n"

using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-9;
const int INF = 0x3f3f3f3f;

ll a[20],m;
ll n,ans;
 
ll lcm(ll a,ll b)
{
    return a/__gcd(a,b)*b;
}
 
void dfs(ll c,ll  cur,ll  i,ll ans1)      //dfs(c,1,i,0,1);
{
    if(cur==c+1)
    {
        if(c&1)
            ans-=n/ans1;
        else
            ans+=n/ans1;
        return;
    }
    for(;i<m;i++)
    {
        dfs(c,cur+1,i+1,lcm(ans1,a[i]));
    }
}

int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    //}
    while(scanf("%lld %lld",&n,&m)!=EOF)
    {
        for(ll i=0;i<m;i++)
            scanf("%lld",&a[i]);
        ans=n;
        for(ll c=1;c<=m;c++)
            dfs(c,1,0,1);
        printf("%lld\n",ans);
    }
#ifdef DEBUG
    printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}