题意：

给一个N，然后给M个数，问1~N-1里面有多少个数能被这M个数中一个或多个数整除。

思路：

首先要N--

然后对于每个数M 其实1~N-1内能被其整除的 就是有(N-1)/M[i]个

但是会出现重复 比如 样例 6就会被重复算 

这时候我们就需要容斥原理了

加上一个数的减去两个数的。。

这里要注意了 两个数以上的时候 是求LCM而不是简单的相乘！

代码：

[cpp] view plaincopy

1. #include "stdio.h"  
2. #include "string.h"  
3. #include "math.h"  
4. #include "iostream"  
5. #include "cstdlib"  
6. #include "algorithm"  
7. #include "queue"  
8. using namespace std;  
9. int a[12];  
10. int used[12],b[12];  
11. int n,m;  
12. int gcd(int a,int b)  
13. {  
14.     return b==0?a:gcd(b,a%b);  
15. }  
16. int lcm(int k)  
17. {  
18.     int ans=b[0];  
19.     for(int i=1;i<k;i++)  
20.     {  
21.         int tep=gcd(ans,b[i]);  
22.         ans=ans/tep*b[i];  
23.     }  
24.     return ans;  
25. }  
26. __int64 dfs(int kk,int x,int lit)  
27. {  
28.     __int64 ans=0;  
29.     if(x==lit)  
30.     {  
31.         int tep;  
32.         tep=lcm(x);  
33.         return n/tep;  
34.     }  
35.     for(int i=kk+1;i<m;i++)  
36.     {  
37.         if(a[i]==0) continue;  
38.         if(used[i]) continue;  
39.         used[i]=1;  
40.         b[x]=a[i];  
41.         ans+=dfs(i,x+1,lit);  
42.         used[i]=0;  
43.     }  
44.     return ans;  
45. }  
46. int main()  
47. {  
48.     while(scanf("%d%d",&n,&m)!=-1)  
49.     {  
50.         n--;  
51.         for(int i=0;i<m;i++) scanf("%d",&a[i]);  
52.         __int64 ans=0;  
53.         for(int i=1;i<=m;i++)  
54.         {  
55.            // printf("%d\n",dfs(-1,0,i));  
56.             memset(used,0,sizeof(used));  
57.             if(i%2==0) ans-=dfs(-1,0,i);  
58.             else ans+=dfs(-1,0,i);  
59.         }  
60.         printf("%I64d\n",ans);  
61.     }  
62.     return 0;  
63. }  

[容斥原理] hdu 1796 How many integers can you find