简单容斥定理-hdu-1796-How many integers can you find
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1796
题目大意：
给一个n，给m个数，求出1~n中能够被m中某个数整除的数的个数。
解题思路：
简单容斥，不解释。
先对m个除掉0，然后数排序，然后容斥。每次求出前面的最小公倍数。
注意：
10 2
2 11 keys:4
10 2
11 2 keys:4
代码：
#include<iostream>#include<cmath>#include<cstdio>#include<cstdlib>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#define eps 1e-6#define INF 0x1f1f1f1f#define PI acos(-1.0)#define ll __int64#define lson l,m,(rt<<1)#define rson m+1,r,(rt<<1)|1#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;//freopen("data.in","r",stdin);//freopen("data.out","w",stdout);ll pp[15],cnt,n;ll ans;ll gcd(ll a,ll b){ if(a%b==0) return b; return gcd(b,a%b);}ll lcm(ll a,ll b){ return a/gcd(a,b)*b;}void dfs(ll la,ll pos,ll flag){ if(pos>cnt) return ; for(int i=pos;i<=cnt;i++) { ll t=(n-1)/lcm(la,pp[i]); if(flag) ans+=t; else ans-=t; dfs(lcm(la,pp[i]),i+1,flag^1); }}int main(){ while(~scanf("%I64d",&n)) { cnt=0; int m; scanf("%d",&m); for(int i=1;i<=m;i++) { ll a; scanf("%I64d",&a); if(a) pp[++cnt]=a; } sort(pp+1,pp+cnt+1); //排序 不排序是有问题的 ans=0; dfs(1,1,1); printf("%I64d\n",ans); } return 0;}