How many integers can you find

    Total Submission(s): 4848 Accepted Submission(s): 1388

    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. 0Output For each case, output the number.

    Sample Input

12 22 3

    Sample Output

7

    Author wangye

    Source 2008 “Insigma International Cup” Zhejiang Collegiate Programming Contest - Warm Up（4）

    已知n和m，有m个元素，求小于n且是m个元素中任意元素的倍数的个数，

HDU 1796 How many integers can you find 容斥原理

//904MS	1596K#include<stdio.h>#include<string.h>int s[27],vis[27],sum,n,m,k;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 x,int ans,int now)//x代表当前第几个数，ans代表一共ans个数求lcm,now代表当前有now个数{    if(now==ans)    {        int a=1;        for(int i=1;i<=k;i++)            if(vis[i])a=lcm(a,s[i]);        if(ans&1)sum+=(n-1)/a;        else sum-=(n-1)/a;        return ;    }    for(;x<=k;x++)        if(!vis[x])        {            vis[x]=1;            dfs(x+1,ans,now+1);            vis[x]=0;        }}int main(){    while(scanf(%d%d,&n,&m)!=EOF)    {        int a;        k=0,sum=0;        for(int i=1;i<=m;i++)        {            scanf(%d,&a);            if(a)s[++k]=a;        }        for(int i=1;i<=k;i++)        {            memset(vis,0,sizeof(vis));            dfs(1,i,0);        }        printf(%d,sum);    }    return 0;}</string.h></stdio.h>