首页 > 搜索 > DFS搜索 > HDU 1796 How many integers can you find-数论-[解题报告] C++
2013
12-23

HDU 1796 How many integers can you find-数论-[解题报告] C++

How 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.

输入:

  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.

输出:

  For each case, output the number.

样例输入:

12 2
2 3

样例输出:

7

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1796

题目大意:给定n和一个大小为m的集合,集合元素为非负整数。为1…n内能被集合里任意一个数整除的数字个数。n<=2^31,m<=10

解题思路:容斥原理地简单应用。先找出1…n内能被集合中任意一个元素整除的个数,再减去能被集合中任意两个整除的个数,即能被它们两只的最小公倍数整除的个数,因为这部分被计算了两次,然后又加上三个时候的个数,然后又减去四个时候的倍数…这题很多人通过深搜来进行,我懒得写深搜,直接枚举状态0…(1<<m),然后判断状态内涵几个集合元素,然后计算lcm和能被整除的个数,最后判断下集合元素的个数为奇还是偶,奇加偶减。

     这题有个地方很无聊,集合里面会混进0,0混进来要先删掉它才不至于在求gcd,lcm的时候RE,0本身对结果没什么影响。

测试数据:

12 2

2 3


12 3

1 2 3


12 4

1 2 3 0


OutPut

7

11

11


C艹代码:

#include <stdio.h>
#include <string.h>


int ans,n,m;
int arr[200],cnt;
int select[200],Lcm;


int gcd(int n,int m) {

	int r = n % m;
	while (r) {

		n = m,m = r;
		r = n % m;
	}
	return m;
}
int lcm(int n,int m) {

	return n / gcd(n,m) * m;
}
int Solve(int n) {

	int i,j,k;


	for (ans = 0, i = 1; i < (1<<m); ++i) {

		cnt = 0;
		for (j = 0; j < m; ++j)
			if (i & (1<<j)) select[++cnt] = j;
		

		for (Lcm = j = 1; j <= cnt; ++j) 
			Lcm = lcm(Lcm,arr[select[j]]);


		if (cnt % 2 == 1)  ans += n / Lcm;
		else ans -= n / Lcm;
	}
	return ans;
}



int main()
{
	int i,j,k;


	while (scanf("%d%d",&n,&m) != EOF) {

		for (i = 0; i < m; ++i) {
		
			scanf("%d",&arr[i]);
			if (arr[i] == 0) i--,m--;
		}
		printf("%d\n",Solve(n-1));
	}
}

本文ZeroClock原创,但可以转载,因为我们是兄弟。

解题报告转自:http://blog.csdn.net/woshi250hua/article/details/7828745


  1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  2. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”