HDU - 1796How many integers can you find 容斥原理

Now you get a number N, and a M-integers set, you should find out how many integers which are small than N, that they can divided exactly by any integers in the set. For example, N=12, and M-integer set is {2,3}, so there is another set {2,3,4,6,8,9,10}, all the integers of the set can be divided exactly by 2 or 3. As a result, you just output the number 7.

Input

  There are a lot of cases. For each case, the first line contains two integers N and M. The follow line contains the M integers, and all of them are different from each other. 0<N<2^31,0<M<=10, and the M integer are non-negative and won’t exceed 20.

Output

  For each case, output the number.

Sample Input

12 2 2 3

Sample Output

7

题解：发现数据并不大最多10个，状压一下，容斥即可

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define lowbit(x) (x&(-x)) #define INF 0x3f3f3f3f const int N=12; typedef long long ll; ll n,m,a[N]; int main() { while(scanf("%lld%lld",&n,&m)!=EOF) { int len=0; for(ll i=1;i<=m;i++) { ll x; scanf("%lld",&x); if(x) a[++len]=x; } m=len; ll mm=(1<<m)-1; ll ans=0; n--; for(ll i=1;i<=mm;i++) { ll tmp=i; ll cnt=0; ll res=1; while(tmp) { if(tmp&1) cnt++; tmp/=2; } for(int j=1;j<=m;j++) { if(i&(1<<(j-1))) { res=res*a[j]/__gcd(res,a[j]); } } if(cnt&1) ans+=n/res; else ans-=n/res; } printf("%lld\n",ans); } return 0; }