简单容斥定理-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;}