hdu 1796 How many integers can you find (容斥原理)
hdu1796 题意：给出n（<=2^31）以及m(<=10)个元素组成的无重复元素集合，集合元素0<=a[i]<=20,问有多少个小于n的数能至少被集合中的一个元素整除。
思路：容斥，找到能被一个元素的，被两个元素的…加加减减。 一个元素的最小公倍数定义成自己，然后多个元素的就两个两个算…
一个坑点是，a[i]有0，而一个数除以0没有意义。。。所以读入的时候处理下。。。把0删掉（个人觉得这个坑点毫无技术含量。。。。0不能作为除数这种事情呵呵呵） 并且如果只有一个数且为0，那么删掉后集合就为空了，特判输出0.
另一个坑点是，别看每个数都很小。。但是求多个数的最小公倍数的时候会爆int…
**虽然最后结果没有爆，但是中间量会爆掉，要开long long **
1/* ***********************************************
2Author :111qqz
3Created Time :2016年02月29日 星期一 19时09分31秒
4File Name :code/hdu/1796.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33int n,m;
34int a[15];
35int b[15];
36
37LL gcd ( LL a,LL b)
38{
39 if (b>a) return gcd(b,a);
40 if (a%b==0) return b;
41 return gcd(b,a%b);
42}
43
44LL lcm( LL a,LL b)
45{
46 LL res;
47 res = a*b; //10个数的最小公倍数会爆掉...虽然最终结果不会，但是乘的这一步会，所以要long long
48 res = res/gcd(a,b);
49 return res;
50}
51int main()
52{
53 #ifndef ONLINE_JUDGE
54 freopen("code/in.txt","r",stdin);
55 #endif
56
57 while (~scanf("%d %d",&m,&n)) //m,n和题目中的意思相反，实在看着别扭
58 {
59 int cnt = 0 ;
60 bool zero = false;
61 for ( int i = 0 ; i < n ; i++)
62 {
63 scanf("%d",&b[i]);
64 if (b[i])
65 {
66 a[cnt++] = b[i];
67 }
68 else
69 {
70 zero = true;
71 }
72 }
73
74 if (cnt==0) //只有一个元素且是0...0不能做除数啊。。。这题好蠢
75 {
76 puts("0");
77 continue;
78 }
79
80
81
82 n = cnt;
83
84 LL ans = 0LL ;
85 for ( int msk = 1 ; msk < (1<<n) ; msk++)
86 {
87 int bits = 0 ;
88 LL LCM;
89 for ( int i = 0 ; i < n ; i++)
90 {
91
92 if (msk&(1<<i))
93 {
94 bits++;
95 if (bits==1)
96 {
97 LCM = a[i];
98 }
99 else
100 {
101 LCM = lcm(LCM,LL(a[i]));
102 }
103 }
104 }
105
106 //cout<<"LCM:"<<LCM<<endl;
107 if (bits%2==1)
108 {
109 ans +=LL((m-1)/LCM);
110 }
111 else
112 {
113 ans -=LL((m-1)/LCM);
114 }
115
116 }
117 printf("%lld\n",ans);
118 }
119
120 #ifndef ONLINE_JUDGE
121 fclose(stdin);
122 #endif
123 return 0;
124}
20160305update:也写个递归版本的，好简洁有木有。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年03月05日 星期六 15时23分46秒
4File Name :code/hdu/r1796.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33int n;
34LL m ;
35int a[15];
36int b[15];
37LL LCM;
38LL ans;
39
40LL gcd ( LL a,LL b)
41{
42 if (b>a) return gcd(b,a);
43 if (a%b==0) return b;
44 return gcd(b,a%b);
45}
46
47LL lcm( LL a,LL b)
48{
49 LL res;
50 res = a*b; //10个数的最小公倍数会爆掉...虽然最终结果不会，但是乘的这一步会，所以要long long
51 res = res/gcd(a,b);
52 return res;
53}
54
55void dfs( int id ,LL x,int flag)
56{
57 ans +=flag*(m-1)/x;
58 for ( int i = id+1 ; i < n ; i++)
59 dfs(i,lcm(x,1LL*a[i]),-1*flag);
60
61}
62int main()
63{
64 #ifndef ONLINE_JUDGE
65 freopen("code/in.txt","r",stdin);
66 #endif
67
68 while (~scanf("%lld %d",&m,&n)) //m,n和题目中的意思相反，实在看着别扭
69 {
70 int cnt = 0 ;
71 bool zero = false;
72 for ( int i = 0 ; i < n ; i++)
73 {
74 scanf("%d",&b[i]);
75 if (b[i])
76 {
77 a[cnt++] = b[i];
78 }
79 else
80 {
81 zero = true;
82 }
83 }
84 if (cnt==0) //只有一个元素且是0...0不能做除数啊。。。这题好蠢
85 {
86 puts("0");
87 continue;
88 }
89
90 ans = 0LL;
91 n = cnt;
92 LCM = 0;
93 for ( int i = 0 ; i < n ; i ++)
94 {
95 dfs(i,a[i],1);
96 }
97 printf("%lld\n",ans);
98 }
99
100 #ifndef ONLINE_JUDGE
101 fclose(stdin);
102 #endif
103 return 0;
104}