Time Limit: 12000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6710 Accepted Submission(s): 1946
题目大意：给定n和一个大小为m的集合，集合元素为非负整数。为1...n内能被集合里任意一个数整除的数字个数。n<=2^31,m<=10
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long Ull;
#define MM(a,b) memset(a,b,sizeof(a));
const double eps = 1e-10;
const int inf =0x7f7f7f7f;
const double pi=acos(-1);
const int maxn=40000;
ll gcd(ll a,ll b)
{
if(b==0) return a;
else return gcd(b,a%b);
}
ll lcm(ll a,ll b)
{
return (a/gcd(a,b))*b;
}
int n,m,bit,mm[24],tmp,cnt;
ll mult;
void solve(int flag)
{
mult=1;bit=0;
for(int i=0;i<cnt;i++)
if(flag&(1<<i))
{mult=lcm(mm[i],mult);bit++;}
}
int main()
{
while(~scanf("%d %d",&n,&m))
{
ll ans=0;n--;cnt=0;
for(int i=0;i<m;i++)
{
scanf("%d",&tmp);
if(tmp) mm[cnt++]=tmp;
}
for(int i=1;i<(1<<cnt);i++)
{
solve(i);
int num=((ll)n)/mult;
if(bit%2==1) ans+=num;
else ans-=num;
}
printf("%lld\n",ans);
}
return 0;
}
分析：很好的一道容斥题，分析：求出在给定区间中能被集合中任意一个数整除的点的个数，分析题目的话
可以发现，先求出区间中所有能被集合中单个数整除的点的个数，求和后，会发现，能同时被两个数整除的点（是这两个数的最小公倍数的倍数）多算了一次，所以就减去能同时被两个数整除点的总个数，然后再加上能同时被三个点减去的点的个数.....(容斥)，不过这个题目有个很大的坑点，就是必须要去0，否则不仅会导致re，而且还会直接导致错误，因为在下面这段代码中，如果cnt换成m的话。可以发现0的存在就直接导致了ans的值得变化，所以必须要在读入集合时就直接将0剔除
for(int i=1;i<(1<<cnt);i++)
{
solve(i);
int num=((ll)n)/mult;
if(bit%2==1) ans+=num;
else ans-=num;
}
hdu 1796 How many integers can you find 容斥第一题
原文：http://www.cnblogs.com/smilesundream/p/5656565.html