How many integers can you find

Time Limit : 12000/5000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 95   Accepted Submission(s) : 30

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

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

2008 “Insigma International Cup” Zhejiang Collegiate Programming Contest – Warm Up（4）
——————————————————————————————————题目的意思是给出一个n和m个数求小于n的有多少个是m个数任意个的倍数
求出，每个数和他们任意的倍数的个数利用容斥原理解决 在求个数时可以用DFS

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>using namespace std;#define LL long long
const int inf=0x7fffffff;
LL a[100];struct node
{
    LL num;
    int cnt;
}ans[100005];int tot,m;
LL n;
LL gcd(LL a,LL b)
{
    return b==0?a:gcd(b,a%b);
}void dfs(int pos,LL lcm,int cnt)
{
    if(pos>=m)
    {
        if(cnt==0)
            return;
        ans[tot].num=(n-1)/lcm;
        ans[tot++].cnt=cnt;
        return;
    }
    if(a[pos]==0)
        dfs(pos+1,lcm,cnt);
    else
    {
        dfs(pos+1,lcm*a[pos]/gcd(lcm,a[pos]),cnt+1);
        dfs(pos+1,lcm,cnt);
    }}int main()
{
    while(~scanf("%lld%d",&n,&m))
    {
        for(int i=0; i<m; i++)
        {
             scanf("%lld",&a[i]);        }        tot=0;
        dfs(0,1,0);
        LL ass=0;
        for(int i=0; i<tot; i++)
        {
            if(ans[i].cnt%2)
                ass+=ans[i].num;
            else
                ass-=ans[i].num;
        }
        printf("%lld\n",ass);
    }
    return 0;
}