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 **
/* ***********************************************
Author :111qqz
Created Time :2016年02月29日 星期一 19时09分31秒
File Name :code/hdu/1796.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6int n,m;
7int a[15];
8int b[15];
1LL gcd ( LL a,LL b)
2{
3 if (b>a) return gcd(b,a);
4 if (a%b==0) return b;
5 return gcd(b,a%b);
6}
1LL lcm( LL a,LL b)
2{
3 LL res;
4 res = a*b; //10个数的最小公倍数会爆掉...虽然最终结果不会，但是乘的这一步会，所以要long long
5 res = res/gcd(a,b);
6 return res;
7}
8int main()
9{
10 #ifndef ONLINE_JUDGE
11 freopen("code/in.txt","r",stdin);
12 #endif
1 while (~scanf("%d %d",&m,&n)) //m,n和题目中的意思相反，实在看着别扭
2 {
3 int cnt = 0 ;
4 bool zero = false;
5 for ( int i = 0 ; i < n ; i++)
6 {
7 scanf("%d",&b[i]);
8 if (b[i])
9 {
10 a[cnt++] = b[i];
11 }
12 else
13 {
14 zero = true;
15 }
16 }
1 if (cnt==0) //只有一个元素且是0...0不能做除数啊。。。这题好蠢
2 {
3 puts("0");
4 continue;
5 }
n = cnt;
1 LL ans = 0LL ;
2 for ( int msk = 1 ; msk < (1<<n) ; msk++)
3 {
4 int bits = 0 ;
5 LL LCM;
6 for ( int i = 0 ; i < n ; i++)
7 {
1 if (msk&(1<<i))
2 {
3 bits++;
4 if (bits==1)
5 {
6 LCM = a[i];
7 }
8 else
9 {
10 LCM = lcm(LCM,LL(a[i]));
11 }
12 }
13 }
1 //cout<<"LCM:"<<LCM<<endl;
2 if (bits%2==1)
3 {
4 ans +=LL((m-1)/LCM);
5 }
6 else
7 {
8 ans -=LL((m-1)/LCM);
9 }
1 }
2 printf("%lld\n",ans);
3 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}
20160305update:也写个递归版本的，好简洁有木有。
/* ***********************************************
Author :111qqz
Created Time :2016年03月05日 星期六 15时23分46秒
File Name :code/hdu/r1796.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6int n;
7LL m ;
8int a[15];
9int b[15];
10LL LCM;
11LL ans;
1LL gcd ( LL a,LL b)
2{
3 if (b>a) return gcd(b,a);
4 if (a%b==0) return b;
5 return gcd(b,a%b);
6}
1LL lcm( LL a,LL b)
2{
3 LL res;
4 res = a*b; //10个数的最小公倍数会爆掉...虽然最终结果不会，但是乘的这一步会，所以要long long
5 res = res/gcd(a,b);
6 return res;
7}
1void dfs( int id ,LL x,int flag)
2{
3 ans +=flag*(m-1)/x;
4 for ( int i = id+1 ; i < n ; i++)
5 dfs(i,lcm(x,1LL*a[i]),-1*flag);
1}
2int main()
3{
4 #ifndef ONLINE_JUDGE
5 freopen("code/in.txt","r",stdin);
6 #endif
1 while (~scanf("%lld %d",&m,&n)) //m,n和题目中的意思相反，实在看着别扭
2 {
3 int cnt = 0 ;
4 bool zero = false;
5 for ( int i = 0 ; i < n ; i++)
6 {
7 scanf("%d",&b[i]);
8 if (b[i])
9 {
10 a[cnt++] = b[i];
11 }
12 else
13 {
14 zero = true;
15 }
16 }
17 if (cnt==0) //只有一个元素且是0...0不能做除数啊。。。这题好蠢
18 {
19 puts("0");
20 continue;
21 }
1 ans = 0LL;
2 n = cnt;
3 LCM = 0;
4 for ( int i = 0 ; i < n ; i ++)
5 {
6 dfs(i,a[i],1);
7 }
8 printf("%lld\n",ans);
9 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}