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;
}