$\Huge\color{orchid}{点击此处获取更多干货}$

容斥原理

本问题与欧拉函数类似，如果受到了欧拉函数的启发，就很容易想到用总数$n$减去$1\sim n$中“不能整除任何一个质数”的数量这个方法，但是本问题并没有保证$n$能够整除每一个质数$p$，那么这样的方法就不适用了。而本问题适用另一个更通用的方法，即容斥原理。

考研数学概率论中关于两事件$A,B$同时发生的概率，有一个更通用的结论：$P(AB)=P(A)+P(B)-P(A\cap B)$，衍生到三事件$A,B,C$，则$P(ABC)=P(A)+P(B)+P(C)-P(A\cap B)-P(B\cap C)-P(A\cap C)+P(A\cap B\cap C)$。由此得出，对于$n$个事件$A_1\sim A_n$，其同时发生的概率$P(A_1A_2…A_n)$可以用$\sum(-1)^{J_S+1}*P(S)$表示。其中$S$为$A_1,A_2,…A_n$中任意事件的交集，$J_S$表示相交构成$S$的事件$A_i$的数量。该求和式暗含了一个信息，就是如果事件$S$由奇数个$A_i$相交而成，那么在结果中就需要累加$P(S)$；如果事件$S$由偶数个$A_i$相交而成，那么在结果中就需要减去$P(S)$。在该问题中，事件$A_i$为“在$1\sim n$中选出一个数，它能被质数$p_i$整除，其概率为$P(A_i)=\frac{\lfloor n/p_i \rfloor}{n}$，分子就是能被$p_i$整除的数量，它同样适用容斥原理。多个事件$A_i$相交时的概率则需要把上式中的$p_i$换成若干$p$的乘积。所有的$p$构成的集合中，每一个元素被选中的情况，可以用若干二进制位来表示。1代表选中，0代表未选中。这个方法，在之后的状态压缩中也会用到。

C++ 代码

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int* primes = new int[m];
    int ans = 0;
    for (int i = 0; i < m; i++) cin >> primes[i];
    for (int i = 1; i < 1 << m; i++) {              //用m位二进制数表示各质数参不参与除法
        size_t divisor = 1, cnt = 0;
        for (int j = 0; j < m; j++) {
            if ((i >> j) & 1) {                     //右移取得每一位
                cnt++;
                divisor *= primes[j];               //除数累乘
                if (divisor > n) break;             //超过n的话，不大于n的整数中不可能存在整除现象，直接结束
            }
        }
        if (divisor > n) continue;                  //同理，不用考虑
        if (cnt % 2 == 1) ans += n / (int)divisor;  //按照容斥原理，增加或减少
        else ans -= n / (int)divisor;
    }
    cout << ans << endl;
    delete[] primes;
    return 0;
}