How many integers can you find(hdu1796)

How many integers can you find

Time Limit: 12000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6429 Accepted Submission(s): 1847

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

思路：容斥原理；需要注意的是给你的数有可能包含0，只要把0换成比n-1大的数或者去掉就行；

还有求的是<n的，那么这时麻烦的地方就是要判断整除，所以转变下就是求(<=n-1)就行这时不需要判断是否整除。

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<stdlib.h>
 5 #include<string.h>
 6 #include<vector>
 7 #include<queue>
 8 #include<stack>
 9 using namespace std;
10 long long  gcd(long long n,long long  m);
11 int ans[20];
12 int main(void)
13 {
14         int i,j,k;
15         int n,m;
16         while(scanf("%d %d",&n,&m)!=EOF)
17         {
18                 int sum=0;
19                 n=n-1;
20                 for(i=0; i<m; i++)
21                 {
22                         scanf("%d",&ans[i]);
23                 }
24                 for(i=0; i<m; i++)
25                 {
26                         if(ans[i]==0)
27                                 ans[i]=n+1;
28                 }
29                 for(i=1; i<=(1<<m)-1; i++)
30                 {
31                         int cnt=0;
32                         long long  an=1;
33                         int flag=0;
34                         for(j=0; j<m; j++)
35                         {
36                                 if(i&(1<<j))
37                                 {
38                                         cnt++;
39                                         long long  cc=gcd(an,(long long)ans[j]);
40                                         an=an/cc*ans[j];
41                                         if(an>n)
42                                         {
43                                                 flag=1;
44                                                 break;
45                                         }
46                                 }
47                         }
48                         if(flag)
49                                 continue;
50                         else
51                         {
52                                 if(cnt%2)
53                                         sum+=n/(int)an;
54                                 else  sum-=n/(int)an;
55                         }
56                 }
57                 printf("%d
",sum);
58         }
59         return 0;
60 }
61 long long  gcd(long long  n,long long  m)
62 {
63         if(m==0)
64                 return n;
65         else if(n%m==0)
66                 return m;
67         else return gcd(m,n%m);
68 }

油！油！you@