hdu1796 How many integers can you find

本文主要是介绍hdu1796 How many integers can you find，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题：http://acm.hdu.edu.cn/showproblem.php?pid=1796

用到了容斥原理。看到了很好的算法，直接采用了。

#include<iostream>
#include<cstdio>
#include<cstring>using namespace std;
typedef __int64 int64;int n, m, cnt, i, j, x;
int64 ans, a[30];int64 gcd(int64 a, int64 b)
{return b == 0 ? a : gcd(b, a % b);
}//id 为1 的时候， 计算本身集合的数量。id为2的时候， 计算重叠；
//反复加减， 不计算后面的情况，有点DP的味道。
void DFS(int cur, int64 lcm, int id)//i, a[i], 1
{lcm = a[cur] / gcd(a[cur], lcm) * lcm;if (id & 1)ans += (n - 1) / lcm;     //因为这题并不包含n本身，所以用n-1elseans -= (n - 1) / lcm;for (int i = cur + 1; i < cnt; i++)DFS(i, lcm, id + 1);
}int main()
{while (~scanf("%d%d", &n, &m))//~end of file{cnt = 0;ans = 0;while (m--){scanf("%d", &x);if (x != 0)    //除0的情况a[cnt++] = x;}for (i = 0; i < cnt; i++)DFS(i, a[i], 1);printf("%d\n", ans);}return 0;
}

这篇关于hdu1796 How many integers can you find的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---