容斥原理

\(\because C_n^0 + C_n^1 + C_n^2 + \ldots + C_n^n = 2^n\)

\(\therefore C_n^1 + C_n^2 + \ldots + C_n^n = 2^n - 1\)

实现的时候，奇数加，偶数减。

题意：给定一个整数 n 和 m 个不同的质数 \(p_1, p_2, \ldots, p_m\) 。求 1 ~ n 中能被 \(p_1, p_2, \ldots, p_m\) 中至少一个数整除的整数有多少个。

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

typedef long long LL;

const char nl = '\n';
const int N = 25;

int p[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) cin >> p[i];

    int res = 0;
    for (int i = 1; i < 1 << m; ++i){
        int t = 1, cnt = 0;
        for (int j = 0; j < m; ++j){
            if (i >> j & 1){
                ++cnt;
                if ((LL)t * p[j] > n){
                    t = -1;
                    break;
                }
                t *= p[j];
            }
        }
        if (t != -1){
            if (cnt & 1) res += n / t;
            else res -= n / t;
        }
    }
    cout << res << nl;

    return 0;
}