[ACM] HDU 1796 How many integers can you find (容斥原理）

How many integers can you find

Problem Description

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 22 3

Sample Output

7

Author

wangye

Source

2008 “Insigma International Cup” Zhejiang Collegiate Programming Contest – Warm Up（4）

到现在才学习容斥….以前见到过好多次这个题，都没认真做….

给定一个包括m个数的集合，数不超过20,问有多少个<n的数，能够被集合中的数整除。关键问题是重复计算，比如6可以被2整除，也可以被3整除，计数了两次，所以要用到容斥原理。容斥就是对于重叠次数只有奇数次的，我们加上，重叠次数为偶数次的，我们要减去。对于每个数，都计算重叠一次的，重叠两次的，重叠三次的…最多重叠m次,有m个数所以要用到DFS，然后保存中间态重叠x次的最小公倍数lcm,符合题意的数有(n-1)/lcm个（** 1~n之间有多少个能被x整除的数，公式为n/x，题目中要求小于n,所以(n-1)/x **），根据step重叠的次数或者加上，或者减去。比如n=7,m=2,集合中的数为2 3首先对于2，重叠一次，lcm=2，7/2=3，有3个符合的数（其实是2,4,6)，因为重叠次数是奇数，所以ans+=3,这时中间态lcm=2，然后继续dfs剩下的数（因为要和其它数组和在一块进行重叠,这里只剩下3了）,重叠两次， lcm=LCM(lcm,3), lcm=LCM(2,3)=6，7/6=1，重叠次数为偶数，ans-=1，这样以2开始的所有情况就完了。再对于3，重叠一次，lcm=3,7/3=2,有两个符合的数，ans+=2.最终ans=4

#include <iostream>#include <stdio.h>#include <algorithm>#include <string.h>#include <stdlib.h>#include <cmath>#include <iomanip>#include <vector>#include <set>#include <map>#include <stack>#include <queue>#include <cctype>#define rd(x) scanf("%d",&x)#define rd2(x,y) scanf("%d%d",&x,&y)#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)using namespace std;typedef long long ll;const int inf=0x3f3f3f3f;const int maxn=25;ll num[maxn];//寸有效数字int cnt;ll ans;ll n,m;ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}ll LCM(ll a,ll b){return a*b/gcd(a,b);}void dfs(int th,ll now,int step)//th，该数是num中的第几个，now是当前的最小公倍数，step是重叠几次，最多cnt次{if(step>cnt)return;ll lcm=LCM(num[th],now);//这里lcm是step个数的最小公倍数if(step&1)ans+=(n-1)/lcm;//1~n之间有多少个能被x整除的数，公式为n/x，题目中要求小于n,所以(n-1)/xelseans-=(n-1)/lcm;for(int p=th+1;p<cnt;p++)dfs(p,lcm,step+1);}int main(){while(scanf("%I64d%I64d",&n,&m)!=EOF){cnt=0;ans=0;ll val;while(m–){scanf("%I64d",&val);if(val>0&&val<n)num[cnt++]=val;}for(int i=0;i<cnt;i++)//从每个数开始，搜索重叠一次，两次，三次….{dfs(i,num[i],1);}printf("%I64d\n",ans);}return 0;}

第二种方法：枚举二进制位

将符合条件的m个数，看作m位，每位是0或者是1，那么一共有2^m种状态，只要判断一下每一个状态有多少个1，也就是有多少个数（重叠多少次）,记为k，每一个1代表哪几个具体的数，求这几个数的最小公倍数，然后(n-1)/lcm, 利用k的值来判断应该减去还是加上。

#define rd(x) scanf("%d",&x)#define rd2(x,y) scanf("%d%d",&x,&y)#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)using namespace std;typedef long long ll;const int inf=0x3f3f3f3f;const int maxn=25;ll num[maxn];//存有效数字int cnt;ll ans;ll n,m;ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}ll LCM(ll a,ll b){return a*b/gcd(a,b);}int main(){while(scanf("%I64d%I64d",&n,&m)!=EOF){cnt=0;ans=0;ll val;for(int i=1;i<=m;i++){scanf("%I64d",&val);if(val>0&&val<n)num[cnt++]=val;}for(int i=1;i<(1<<cnt);i++)//把cnt个数看作cnt位，，每位是0或者1{//下面就是求状态i里面有多少个1，也就是重叠多少次，用k表示int k=0;ll lcm=1;for(int j=0;j<cnt;j++){if(i&(1<<j)){k++;lcm=LCM(lcm,num[j]);//求出这k个数的最小公倍数}}if(k&1)ans+=(n-1)/lcm;elseans-=(n-1)/lcm;}printf("%I64d\n",ans);}return 0;}

而现在我喜欢深邃的夜空，包容一切的黑暗和隐忍，留下眼泪也没人看见。