hdu 1796 How many integers can you find 容斥定理

时间：2025-02-17 12:03:26

How many integers can you find

Time Limit: 12000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Problem Description
  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
Author
wangye
Source
思路：最简单的容斥，注意下可能输入0；奇加偶减
　　　比如12 2 
              2   3
　　　　　ans=11/2+11/3-11/6;
#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<set>

#include<map>

using namespace std;

#define ll __int64

#define mod 1000000007

#define inf 999999999

//#pragma comment(linker, "/STACK:102400000,102400000")

int scan()

{

    int res =  , ch ;

    while( !( ( ch = getchar() ) >= '' && ch <= '' ) )

    {

        if( ch == EOF ) return  <<  ;

    }

    res = ch - '' ;

    while( ( ch = getchar() ) >= '' && ch <= '' )

        res = res *  + ( ch - '' ) ;

    return res ;

}

ll a[];

ll ji;

ll ans,x,y;

ll gcd(ll x,ll y)

{

    return y==?x:gcd(y,x%y);

}

void dfs(ll lcm,ll pos,ll step)

{

    if(lcm>x)

    return;

    if(pos==ji)

    {

        if(step==)

            return;

        if(step&)

        ans+=x/lcm;

        else

        ans-=x/lcm;

        return;

    }

    dfs(lcm,pos+,step);

    dfs(lcm/gcd(a[pos],lcm)*a[pos],pos+,step+);

}

int main()

{

    ll z,i,t;

    while(~scanf("%I64d%I64d",&x,&y))

    {

        x--;

        ji=;

        for(i=;i<y;i++)

        {

            scanf("%I64d",&z);

            if(z==)continue;

            a[ji++]=z;

        }

        ans=;

        dfs(,,);

        printf("%I64d\n",ans);

    }

    return ;

}

相关文章