题目链接

• 容斥原理
• 用二进制枚举所有集合的选取情况

• 1~n 中能被p整除的有n/p个，能同时被p1,p2整除的有n/(p1*p2),… (因为p1, p2是互质的)

#include <iostream>
using namespace std;

int n, m, res;
int primes[20];

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

    // 二进制 i 表示所有集合的状态
    for (int i = 1; i < (1 << m); i ++){  // i从1开始而不是0，因为最少也要有1个集合
        int s = 1, t = 0;  // s 是当前二进制i所有质数乘积， t 是 所有质数个数
        for (int j = 0; j < m; j ++){ 
            if ((i >> j) & 1) {
                if ((long long)s * primes[j] > n){   // 如果乘积大于n就可以直接退出了
                    s = 0; break;
                }
                s *= primes[j];
                t ++;
            }
        }
        if (!s) continue;
        if (t & 1) res += n / s;   // 奇数个集合则 + 
        else res -= n / s;    // 偶数个集合则 - 
    }
    cout << res;

    return 0;
}