How many integers can you find（容斥裸）

2018-09-08

How many integers can you find

题意

一个n，一个长度为m的集合，集合里面有m个元素，问小于n的所有能被集合中任意元素整除的数字有多少。

n<2^31,m<=10

看！代码

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

const int MAXN = 25;
int p[MAXN];
int n;
int m;
int Result;

int GCD(int a, int b) { //欧几里得算法，求最大公约数。
    if (b == 0) return a;
    else return GCD(b, a % b); //辗转相除。
}

int LCM(int a, int b) { //求最小公倍数。
    return a / GCD(a, b) * b;
}

int Solve(int n) { //深度优先搜索实现容斥原理。
    int i, j;
    int Cnt_Manifold; //遍历到的数的数量（数集的数量）。
    int Least_Common_Multiple; //遍历到的Cnt_Manifold个数的最小公倍数。
    Result = 0; //记录每次深度搜索的结果。
    for (i = 1; i < (1 << m); i++) { //i的二进制位代表此次遍历查找的是那几个数
        Cnt_Manifold = 0;
        Least_Common_Multiple = 1; //1与任何数的最小公倍数还是那个数本身，所以初值赋为1.
        for (j = 0; j < m; j++)
            if (i & (1 << j)) { //筛选出要找的数并求出他们的最小公倍数。
                Cnt_Manifold++;
                Least_Common_Multiple = LCM(Least_Common_Multiple, p[j]);
            }
        if (Cnt_Manifold & 1) { //奇数个为正偶数个为负，其作用相当于(-1)^(n - 1).
            Result += n / Least_Common_Multiple;
        }
        else {
            Result -= n / Least_Common_Multiple;
        }
    }
    return Result;
}

int main() {
    int cnt;
    int temp;
    while (cin >> n >> m) {
        cnt = 0;
        for (int i = 0; i < m; i++) {
            cin >> temp; //去除了0的情况
            if (temp) {
                p[cnt++] = temp;
            }
        }
        m = cnt;
        cout << Solve(n - 1) << endl;
    }
    return 0;
}