本文主要是介绍HDU 1796 How many integers can you find，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：http://acm.hdu.edu.cn/showproblem.php?pid=1796
How many integers can you find
Time Limit: 12000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5612 Accepted Submission(s): 1608
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 2 2 3
Sample Output
7
Author
wangye
Source
2008 “Insigma International Cup” Zhejiang Collegiate Programming Contest - Warm Up（4）
Recommend
wangye | We have carefully selected several similar problems for you: 1793 1794 1797 1795 1798
大意——给定一个数n和一个具有m个元素的m-集合，要你找出有多少个正整数小于n，并且这些正整数要能被m-集合中的至少一个元素整除。其中0<n<2^31,0<m<=10。
思路——不难发现这是一个裸的简单容斥原理题。容斥原理公式如下图所示：
因此，我们需要找出各个子集的计数，然后按照公式计算。因为是一步一步深入探索，所以可以用深搜实现容斥原理，只是在搜索的过程中要加上符号判断，从而得到正确的结果。
复杂度分析——时间复杂度:O(m+2^cnt),空间复杂度:O(m)
附上AC代码：
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <map>
//#pragma comment(linker, "/STACK:102400000, 102400000")
using namespace std;
typedef unsigned int li;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const double pi = acos(-1.0);
const double e = exp(1.0);
const double eps = 1e-8;
const int maxm = 15; // 集合最大计数
int num[maxm]; // m个数的集合
int n, m, cnt; // 给定数n，集合计数m，不为零的m集合计数
int ans; // 最后所求结果int gcd(int a, int b); // 求最大公约数
int lcm(int a, int b); // 求最小公倍数
void dfs(int index, int common, int sign); // 利用深搜展现容斥原理int main()
{ios::sync_with_stdio(false);while (~scanf("%d%d", &n, &m)){int x; // 集合元素cnt = 0;while (m--){scanf("%d", &x);if (0 == x) // 集合元素可能含有零，丢弃零continue;num[cnt++] = x; // 不为零的元素存入集合}ans = 0; // 初始化最后所求结果for (int i=0; i<cnt; i++)dfs(i, num[i], 1); // 枚举m集合中非零元素进行深搜printf("%d\n", ans);}return 0;
}int gcd(int a, int b)
{ // 欧几里得算法/辗转相除法return b ? gcd(b, a%b) : a;
}int lcm(int a, int b)
{ // 这样写，有利于防止中间过程溢出return a/gcd(a, b)*b;
}void dfs(int index, int common, int sign)
{ // 集合元素的索引，最小公倍数，符号判断(容斥公式中的奇数项加偶数项减)common = lcm(num[index], common);if (sign & 1) // 奇数项加ans += (n-1)/common; // 小于n的数，所以用n-1else // 偶数项减ans -= (n-1)/common;for (int i=index+1; i<cnt; ++i)dfs(i, common, sign+1); // 一层是找出一个元素的子集最小公倍数的计数// 两层是找出两个元素的子集最小公倍数的计数// 以此类推，所有子集最小公倍数的计数都找出
}
这篇关于HDU 1796 How many integers can you find的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
