题目描述

给定一个整数 $n$ 和 $m$ 个不同的质数 $p_1$, $p_2$,…, $p_m$。
请你求出 $1$ ～ $n$ 中能被 $p_1$, $p_2$,…, $p_m$ 中的至少一个数整除的整数有多少个。

算法

容斥原理

记 $1$ ~ $n$ 所有数的集合为 $A$。设性质 $P_i$ 为：$n$ 可以被质数 $p_i$整除。设 $1$ ~ $n$ 中满足性质 $P_i$ 的数所在的集合为 $A_i$，集合大小记为 $\left|A_i\right|$。至少满足 $P_1$, $P_2$, …, $P_m$ 这些性质中至少一个性质的数所在集合显然为
$$ A_1\cup A_2 \cup … \cup A_m$$，则由容斥原理，这个集合的大小为：$$\left| A_1\cup A_2 \cup … \cup A_m \right| = \sum_{i = 1}^{m}\left| A_i \right| - \sum_{\text{$1$~$m$ 的2组合}} \left| A_i \cap A_j \right| + \sum_{\text{$1$~$m$ 的3组合}} \left| A_i \cap A_j \cap A_k \right| + … +(-1)^{m-1}\left| A_1 \cap A_2\cap … \cap A_m \right|$$

对于本题，如果一个数满足多个性质，即可以同时被 $p_{i_1}, p_{i_2}, …, p_{i_k}$整除，则这样的数共有 $$\left\lfloor \frac{n}{p_{i_1} p_{i_2} … p_{i_k}} \right\rfloor$$ 个。因此，问题就回到了给定 $m$ 个质数构成的集合 { $p_1$, $p_2$,…, $p_m$ }，这个集合的所有非空子集。

深度优先搜索实现集合非空子集枚举

将这 $m$ 个数放入数组 $p$ 中，下标范围为 $0$ ~ $m-1$，则问题转化为枚举集合 { $0, 1, …, m-1$ } 所有的非空子集。参考 AcWing 842. 排列数字 ，本题也可以用深度优先搜索。但与排列数字那道题不同的是，一串数字的多个排列有可能对应于一个子集。例如：1 2 3 4 5 和 1 3 2 5 4这两个排列对应于同一个子集 {$1, 2,3,4,5$}。因此，为了避免深度优先搜索的时候出现重复搜索的情况，我们规定搜索的序列必须是单调递增的，即后面搜索到的数必须比前面的数大，这样就能避免因数字的排列引起的重复。例如，在之前的搜索我们得到的结果是 0 1 3 4，那么现在搜索的数的范围（即第 5 个数）必须从 5 开始，排列为 0 1 3 4 5 或 0 1 3 4 6 或 0 1 3 4 7 等等。

下面用归纳法证明上述算法的正确性。对于一个组合序列 $x_1, x_2, …, x_k$，其中 $x_1 < x_2 < … < x_k$。在第一个数的搜索我们会遍历所有的数，因此 $x_1$ 一定会被搜到，因此序列中的 $x_1$ 可以被搜到。假设 $x_1, x_2, …, x_{i-1}$可以这个序列可以成功搜索，由于 $x_i>x_{i-1}$，因此$x_{i}$也可以被搜到，所以序列 $x_1, x_2, …, x_{i-1}, x_{i}$一定会被搜到。因此归纳可得，任意一个组合序列都能被搜索到。

对于每次的搜索，我们需要直到上一级的乘积结果 times，即 $p_{i_1}p_{i_2}…p_{i_{k-1}}$。那么，对于本次搜索到的$p_{i_k}$，直接乘上之前的乘积，得到新的乘积 new_times，便可算出容斥原理中的新的项 $n/(p_{i_1}p_{i_2}…p_{i_{k-1}})$，并据此修改结果变量 res. 但是，应该是加还是减呢？因此，我们还要从上一层接受操作数 op（等于+1或-1）。如果上一层操作数是op，那么传到这层的一定是 -op。这样，结果变量就被修改为 res += op * n / new_times

C++ 代码

/**
 * 本质是组合枚举问题，详见自己写的题解
 */

#include <iostream>

using namespace std;

typedef long long LL;

const int M = 20;

int n, m;
int p[M];

/**
 * s: 当前允许搜索的最小下标
 * times: 前面的质数乘积。注意times变量的类型要取成long long，因为乘积有可能溢出
 * op: 操作数，取+1或-1
 * res: 保存最终结果的变量，由于此变量被引用，因此可以实时被修改
 */
void dfs(int s, LL times, int op, int &res) {
    for (int i = s; i < m; i++) {
        LL new_times = times * p[i];    // 前面的乘积结果乘上这个质数的到新的乘积
        res += op * (n / new_times);    // 将新的项加到结果上
        dfs(i + 1, new_times, -op, res);    // 之后的数从i+1开始搜索，传递乘上pi后的新乘积，并将op取反
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) scanf("%d", p + i);

    int res = 0;
    dfs(0, 1, 1, res);

    printf("%d", res);

    return 0;
}