HDU 1796 How many integers can you find

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int maxn = 20;
 5 int a[maxn],n,m;
 6 LL LCM(LL a,LL b){
 7     return a/__gcd(a,b)*b;
 8 }
 9 int main(){
10     while(~scanf("%d%d",&n,&m)){
11         int tot = m;
12         for(int i = m = 0,tmp; i < tot; ++i){
13             scanf("%d",&tmp);
14             if(tmp) a[m++] = tmp;
15         }
16         LL ret = 0;
17         for(int i = 1; i < (1<<m); ++i){
18             LL lcm = 1;
19             int cnt = 0;
20             bool flag = false;
21             for(int j = 0; j < m; ++j){
22                 if((i>>j)&1){
23                     cnt++;
24                     lcm = LCM(lcm,a[j]);
25                     if(lcm < 0){
26                         flag = true;
27                         break;
28                     }
29                 }
30             }
31             if(flag) continue;
32             if(cnt&1) ret += (n - 1)/lcm;
33             else ret -= (n - 1)/lcm;
34         }
35         printf("%I64d\n",ret);
36     }
37     return 0;
38 }