How many integers can you find

12 2
2 3

7

//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\n",sum);
    }
    return 0;
}