题意：
给一个N。然后给M个数，问1~N-1里面有多少个数能被这M个数中一个或多个数整除。
思路：
首先要N--
然后对于每一个数M 事实上1~N-1内能被其整除的 就是有(N-1)/M[i]个
可是会出现反复 比方 例子 6就会被反复算
这时候我们就须要容斥原理了
加上一个数的减去两个数的。。
这里要注意了 两个数以上的时候 是求LCM而不是简单的相乘！
代码：
#include "stdio.h"
#include "string.h"
#include "math.h"
#include "iostream"
#include "cstdlib"
#include "algorithm"
#include "queue"
using namespace std;
int a[12];
int used[12],b[12];
int n,m;
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
int lcm(int k)
{
int ans=b[0];
for(int i=1;i<k;i++)
{
int tep=gcd(ans,b[i]);
ans=ans/tep*b[i];
}
return ans;
}
__int64 dfs(int kk,int x,int lit)
{
__int64 ans=0;
if(x==lit)
{
int tep;
tep=lcm(x);
return n/tep;
}
for(int i=kk+1;i<m;i++)
{
if(a[i]==0) continue;
if(used[i]) continue;
used[i]=1;
b[x]=a[i];
ans+=dfs(i,x+1,lit);
used[i]=0;
}
return ans;
}
int main()
{
while(scanf("%d%d",&n,&m)!=-1)
{
n--;
for(int i=0;i<m;i++) scanf("%d",&a[i]);
__int64 ans=0;
for(int i=1;i<=m;i++)
{
// printf("%d
",dfs(-1,0,i));
memset(used,0,sizeof(used));
if(i%2==0) ans-=dfs(-1,0,i);
else ans+=dfs(-1,0,i);
}
printf("%I64d
",ans);
}
return 0;
}