ACM: How many integers can you find-数论专题-容斥原理的简单应用+GCD

时间：2021-02-08 13:21:20
How many integers can you find

Time Limit:5000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

 
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 2

2 3

Sample Output

7

/*/

题意：

给出N和M 输入M个数，找出所有M个数的倍数并且，Mi的倍数小于N，输出所有数的总个数。 

如果一个数同时是三个数的倍数

单独记一个数的倍数次数为C（3，1） =3

记两个数的倍数次数为 C（3，2）=3

记三个数的倍数次数为 C（3，3）=1

3-3+1=1，只记一次依次类推

一个数为5个数的倍数

C（5，1）=5

C（5，2）=10

C（5，3）=10

C（5，4）=5

C（5，5）=1

5-10+10-5+1=1

六个数

C（6，1）=6

C（6，2）=15

C（6，3）=20

C（6，4）=15

C（6，5）=6

C（6，6）=1

6-15+20-15+6-1=1

上图：
ACM: How many integers can you find-数论专题-容斥原理的简单应用+GCD

然后因为数字不超过10个，可以运用枚举子集的思想去做这个题目。

所以用到DFS。

最后有一个地方要注意就是在DFS里面判断积这里，要用GCD，一开始没想到过不了样例。 

AC代码：

/*/
#include"map"

#include"cmath"

#include"string"

#include"cstdio"

#include"vector"

#include"cstring"

#include"iostream"

#include"algorithm"

using namespace std;

typedef long long LL;

LL a[15];

int n,m,cnt;

LL ans,x;

LL gcd(LL a,LL b){

	return b?gcd(b,a%b):a;

}

void DFS(int x,LL axb,int num) {

	axb=a[x]/gcd(a[x],axb)*axb;

	if(num&1) ans+=(n-1)/axb;

	else ans-=(n-1)/axb;

	//	cout<<"now ans is:"<<ans<<endl;  //检查

	for(int i=x+1; i<cnt; i++)

		DFS(i,axb,num+1);

}

int main() {

	while(~scanf("%d%d",&n,&m)) {

		ans=0;

		cnt=0;

		for(int i=0; i<m; i++) {

			scanf("%I64d",&x);

			if(x!=0)a[cnt++]=x;

		}

		for(int i=0; i<cnt; i++){

			DFS(i,a[i],1);       //用DFS去枚举每种选择的情况。

		}

		printf("%d\n",ans);

	}

	return 0;

}

　　

相关文章