HDU 1796 How many integers can you find(容斥原理)

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

题目链接

容斥原理的模板题，奇加偶减，用Dfs搜索判断计数即可。

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e2 + 5;

int N, M;
int Tot;
long long Number[maxn];
long long Ans;

int Gcd(int A, int B) {
    return B ? Gcd(B, A % B) : A;
}

void Dfs(int Cur, int Cnt, int Limit, long long LCM) {
    if (Cnt == Limit) {
        if (Limit & 1) {
            Ans += (N - 1) / LCM;
        }
        else {
            Ans -= (N - 1) / LCM;
        }
        return;
    }
    if (Cur >= Tot) {
        return;
    }
    long long NowLCM = LCM == -1 ? Number[Cur] : LCM;
    Dfs(Cur + 1, Cnt + 1, Limit, Number[Cur] / Gcd(Number[Cur], NowLCM) * NowLCM);
    Dfs(Cur + 1, Cnt, Limit, LCM);
}

int main(int argc, char *argv[]) {
    while (~scanf("%d%d", &N, &M)) {
        Tot = 1;
        for (int i = 1, X; i <= M; ++i) {
            scanf("%d", &X);
            if (X != 0) {
                Number[Tot++] = X;
            }
        }
        Ans = 0;
        for (int i = 1; i < Tot; ++i) {
            Dfs(1, 0, i, -1);
        }
        printf("%lld\n", Ans);
    }
    return 0;
}