容斥原理是一个数学计数工具，主要用于计算多个元素集合的并集。它通过加减各个集合的交集，避免重复计数。在组合数学、概率论、数论中广泛应用。

基本公式

假设有 $A_1, A_2, \dots, A_n$ 这$n$个集合，那么这些集合并集的元素总数可以用容斥原理计算为：
$|A_1 \cup A_2 \cup \dots \cup A_n| = \sum_{k=1}^n (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \dots < i_k \leq n} |A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k}|$
具体来说，$n$个集合间隔加减：
1. 加所有单个集合的大小 $|A_i|$
2. 减去所有两两交集的大小$|A_i\cap A_j|$
3. 加上所有三重交集的大小$|A_i \cap A_j \cap A_k|$
如此往复直到$n$重交集
例如 3 个集合的并集大小：
$|A_1 \cup A_2 \cup A_3| = |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_1|$
● $|A_1\cap A_2|$
● $|A_1\cap A_2\cap A_3|$
● 等等…

组合总数：考虑$n$个集合$A_1, A_2, \dots, A_n$ ，每个集合可以在某一交集中，即每个集合有两种选择：
● 出现（包含在某集合中）
● 不出现（不包含在集合中）
因此，每个集合“出现”或“不出现”，对于$n$个集合，一共有$2^n$种组合。
需要注意，在$2^n$种组合中，有一种特殊情况，即“空交集”。容斥原理只考虑非空交集，需要排除这种情况。
综上，在容斥原理公式中，总共有：
$2^n - 1$个非空交集。

解题思路

1. 对于 m 个质数，遍历非空交集共$2^m - 1$种组合。时间复杂度$O(2^m)$
2. 每次遍历，时间复杂度$O(m)$，需要做两件事：
   a. 统计本次组合的交集数量，交集数的奇偶性决定正负；
   b. 确定交集运算结果，即找出有$1 ～ n$中有几个可以被当前选中的所有质数整除的数，要满足被所有质数整除，则计算所有质数的最小公倍数$lcm$，这里都是质数$lcm=\prod_{j=1}^m p_j$（$j$要被选中 )，因此个数为$\lfloor \frac{n}{lcm} \rfloor$。
3. 根据交集数量 bits，加减$\lfloor \frac{n}{lcm} \rfloor$。

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 20;
int p[N];

int main() {
    int n, m;
    cin >> n >> m;

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

    int count = 0;
    // 遍历 2^m - 1 所有组合
    for (int i = 1; i < (1 << m); i++) {
        // 最小公倍数
        LL lcm = 1;
        // 集合质数个数 后面奇偶判断正负
        int bits = 0;
        // 求最小公倍数的过程
        for (int j = 0; j < m; j++) 
            // 第j位被选中
            if (i & (1 << j)) {
                bits ++;
                // 质数间的lcm就是乘积
                lcm *= p[j];
                if (lcm > n) 
                    break;
            }
        // 最小公倍数大于n，则说明这个组合是空集
        if (lcm > n) 
            continue;
        if (bits & 1) {
            count += n / lcm;
        } else {
            count -= n / lcm;
        }
    }

    cout << count << endl;

    return 0;
}