容斥原理

原理

见《进阶指南》第175页。

模板题

AcWing-890-能被整除的数

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 20;
int n, p[N], m; // 1 ~ m

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

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