How many integers can you find

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

Total Submission(s): 5556    Accepted Submission(s): 1593

12 2

2 3

7

题目大意：

求n以内可以被所给的集合中的数整除的数的个数。



解题思路：

这里要运用我们所说的容斥原理。

所谓容斥原理，运用起来要记住“奇加偶减”。

比方求100以内能被2,3,11,13,41整除的数的个数，我们即u(i)为100以内能被i整除的数的个数。

那么答案就是：

u(2)+u(3)+u(11)+u(13)+u(41)

-u(2*3)-u(3*11)-u(11*13)-u(13*41)

+u(2*3*11)+u(3*11*13)+u(11*13*41)

-u(2*3*11*13)-u(3*11*13*41)

+u(2*3*11*13*41)

这就是所谓的“奇加偶减”。

同一时候n以内能被i整除的数的个数为(n-1)/i。

综上。我们就能够通过枚举集合中的数，再容斥来得到答案。

枚举有2中方法：暴力枚举和dfs。因为m最大仅仅有10。暴力枚举时我们能够使用二进制来代表某个状态，每一位代表去与不取。dfs就非常easy了。

參考代码：

/*

二进制

Memory: 1568 KB		Time: 639 MS

Language: G++		Result: Accepted

*/

#include<map>

#include<stack>

#include<queue>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const double eps=1e-10;

const int INF=0x3f3f3f3f;

const int MAXN=25;

typedef long long LL;

int n,m,num[MAXN],divi[MAXN];

int gcd(int a,int b)

{

    return b?gcd(b,a%b):a;

}

int lcm(int a,int b)

{

    return a/gcd(a,b)*b;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("in.txt","r",stdin);

#endif // ONLINE_JUDGE

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        int cnt=0;

        for(int i=0;i<m;i++)

        {

            scanf("%d",&num[i]);

            if(num[i])

                divi[cnt++]=num[i];

        }

        m=cnt;

        int ans=0;

        for(int k=1;k<(1<<m);k++)

        {

            int select=0,tlcm=1;

            for(int i=0;i<m;i++)

            {

                if(k&(1<<i))

                {

                    select++;

                    tlcm=lcm(tlcm,divi[i]);

                }

            }

            if(select&1)

                ans+=(n-1)/tlcm;

            else

                ans-=(n-1)/tlcm;

        }

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

    }

    return 0;

}

/*

dfs

Memory: 1572 KB		Time: 109 MS

Language: G++		Result: Accepted

*/

#include<map>

#include<stack>

#include<queue>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const double eps=1e-10;

const int INF=0x3f3f3f3f;

const int MAXN=25;

typedef long long LL;

int n,m,num[MAXN],divi[MAXN],ans;

int gcd(int a,int b)

{

    return b?

gcd(b,a%b):a;

}

int lcm(int a,int b)

{

    return a/gcd(a,b)*b;

}

void dfs(int pos,int tlcm,int select)

{

    //if(pos>m)

    //    return ;

    tlcm=lcm(tlcm,divi[pos]);

    select++;

    if(select&1)

        ans+=(n-1)/tlcm;

    else

        ans-=(n-1)/tlcm;

    for(int i=pos+1;i<m;i++)

        dfs(i,tlcm,select);

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("in.txt","r",stdin);

#endif // ONLINE_JUDGE

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        int cnt=0;

        for(int i=0; i<m; i++)

        {

            scanf("%d",&num[i]);

            if(num[i])

                divi[cnt++]=num[i];

        }

        m=cnt;

        ans=0;

        for(int i=0;i<m;i++)

            dfs(i,1,0);

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

    }

    return 0;

}