题目描述

给定一个整数n和m个不同的质数p1,p2,…,pm。

请你求出1~n中能被p1,p2,…,pm中的至少一个数整除的整数有多少个。

样例

输入
10 2
2 3
输出
7

算法

（容斥原理）

解决爆int问题， 速度提高了不少。

时间复杂度 O(2 ^ m * m)

C++ 代码

#include <bits/stdc++.h>

#define LL long long

using namespace std;

int n, m, p[20];

int main() {
    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 x = n, cnt = 0;
        for (int j = 0; j < m; j ++ ) if (i >> j & 1) cnt ++, x /= p[j];
        if (cnt & 1) res += x;
        else res -= x;
    }
    cout << res << endl;
    return 0;
}