HDU 1796 How many integers can you find 容斥、lcm

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

题意：

输入n和m个数。问你小于n中，有几个数能够被m个数中的任意一个整除的。

思路：

容斥+lcm（最小公倍数）

设m数组中结果为｛a1，a2，a3，……，am｝;

1.加上n/a1，n/a2，n/a3……的个数。

2.减去n/lcm(a1,a2)，n/lcm(a1*a3)，……，n/lcm(a2*a3)，n/lcm(a2*a4),……；

3.加上三个集合的，然后减去四个集合的，加上五个集合的……

因为m最大为10，因此直接用二进制枚举即可，我用了dfs进行枚举。

code：

#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long LL;int n, m;
LL res;
int a[15];
inline LL gcd(LL sum, LL t)
{return t?gcd(t, sum%t) : sum;
}
inline LL lcm(LL sum, LL t)
{return sum/gcd(sum, t) * t;
}
void dfs(int cnt, int index, LL sum)
{if(index == m){if(cnt != 0 && sum != 0){if(cnt%2)res += (LL)n/sum;elseres -= (LL)n/sum;}return ;}dfs(cnt+1, index+1, lcm(sum, a[index]));dfs(cnt, index+1, sum);
}void solve()
{res = 0;dfs(0, 0, 1);printf("%I64d\n", res);
}int main()
{while(scanf("%d%d", &n, &m) != EOF){n--;for(int i = 0;i < m; i++)scanf("%d", &a[i]);solve();}return 0;
}

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

---