HDU 1796 How many integers can you find(求1到n-1之间能被一个集合A内元素整除的数的个数)_综合

题目链接：
HDU 1796 How many integers can you find
题意：
求 $1-n-1$ 之间能被一个集合 $A$ 内元素整除的数的个数，例如 $n = 12, A = \{2, 3\}$ 则能被 $A$ 集合元素整除的数的集合为 $\{2, 3, 4 , 6, 8, 9, 10\}$ 则结果为 $7$ 。
分析：
容斥原理。
找出 $1...n-1$ 内能被集合中任意一个元素整除的个数，再减去能被集合中任意两个整除的个数，即能被它们两的最小公倍数整除的数的个数，因为这部分被计算了两次，然后又加上三个时候的个数，
然后又减去四个时候的倍数…所以深搜，枚举选择数的个数，奇加偶减。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;
const int MAX_N = 25;ll ans, res;
int m, total;
ll n, data[MAX_N], can[MAX_N];ll gcd(ll a, ll b)
{return b == 0 ? a : gcd(b, a % b);
}ll lcm(ll a, ll b)
{return a / gcd(a, b) * b;
}void dfs(int cur, int cnt, int sum)
{if(cnt == sum){ll tmp = 1;for(int i = 0; i < cnt; i++){tmp = lcm(tmp, can[i]);}res += (n - 1) / tmp;return ;}for(int i = cur; i < total; i++) {can[cnt] = data[i];dfs(i + 1, cnt + 1, sum);}
}int main()
{freopen("1796.in", "r", stdin);while(~scanf("%lld%d", &n, &m)){total  = 0;for(int i = 0; i < m; i++){ll tmp ;scanf("%lld", &tmp);if(tmp){data[total++] = tmp;}}ans = 0;for(int i  = 1; i <= total; i++){res = 0;dfs(0, 0, i);//printf("i = %d res = %lld\n", i, res);if(i & 1) ans += res;else ans -= res;}printf("%lld\n", ans);}return 0;
}

【7、14更】
今天换了一种 $dfs$ 方式
:)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N = 25;ll n, ans;
int m;
ll data[MAX_N];inline ll gcd(ll a, ll b)
{return b == 0 ? a : gcd(b, a % b);
}inline ll lcm(ll a, ll b)
{return a / gcd(a, b) * b;
}void dfs(int cur, int num, int total, ll mul)
{if(num == total) {if(total & 1) ans += n / mul;else ans -= n / mul;return ;}if(cur == m) return;dfs(cur + 1, num, total, mul);dfs(cur + 1, num + 1, total, lcm(mul, data[cur]));
}int main()
{while(~scanf("%lld%d", &n, &m)) {n--;int total = 0;for(int i = 0; i < m; ++i) {ll tmp;scanf("%lld", &tmp);if(tmp) data[total++] = tmp;}m = total;ans = 0;for(int i = 1; i <= m; ++i) {dfs(0, 0, i, 1);}printf("%lld\n", ans);}return 0;
}