能被整除的数

​ 给定一个整数 $n$ 和 $m$ 个不同的质数。求出 $[1,n]$ 能被这些质数中至少一个数整除的数的个数。

容斥原理：

​ 给定 $n$ 个不同的集合 $A_i$，集合之间可能会有重复，求出
$$ \vert\bigcup A_i\vert $$
​ 先从两个集合开始考虑，其结果为：
$$ |A_1| + |A_2| - |A_1 \cap A_2| $$
​ 再考虑三个集合，其结果为：
$$ |A_1|+|A_2|+|A_3|-|A_1 \cap A_2|-|A_1 \cap A_3|-|A_2 \cap A_3|+|A_1\cap A_2 \cap A_3| $$
​ 将这些情况推广到一般，可以发现其结果为：

​ 加上所有奇数个集合交集的基数，减去所有偶数个集合交集的基数。

​ 由此我们可以将各质因子看作集合，此时 $|A_i| = \lfloor\frac{n}{p_i}\rfloor$，$|A_i \cap A_j|=\lfloor\frac{n}{p_ip_j}\rfloor$其他情况同样的道理。再用状态压缩来枚举质数的选取方法，根据选取质数个数来判断加减。

代码 $O(2^m)$

typedef long long ll;

int solve(vector<int> primes, int n){

    int m = primes.size();
    int res = 0;

    for (int i = 1; i < 1 << m; i ++ ){ //i即为二进制压缩的状态

        int cnt = 0, t = 1;

        for (int j = 0; j < m; j ++ ){
            if (i >> j & 1){
                cnt ++ ;
                if ((ll) t * primes[j] > n){
                    cnt = -1;
                    break;
                }
                t *= primes[j];
            }
        }
        if ( ~ cnt){
            res += (cnt & 1 ? 1 : -1) * n / t;
        }
    }

    return res;
}

完整代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int solve(vector<int> primes, int n){

    int m = primes.size();
    int res = 0;

    for (int i = 1; i < 1 << m; i ++ ){

        int cnt = 0, t = 1;

        for (int j = 0; j < m; j ++ ){
            if (i >> j & 1){
                cnt ++ ;
                if ((ll) t * primes[j] > n){
                    cnt = -1;
                    break;
                }
                t *= primes[j];
            }
        }
        if ( ~ cnt){
            res += (cnt & 1 ? 1 : -1) * n / t;
        }
    }

    return res;
}

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> primes;

    while (m -- ){
        int x;
        cin >> x;
        primes.push_back(x);
    }

    cout << solve(primes, n);
}