题解：CF93E Lostborn - 洛谷保存站

MX-C day1 T2。

### 题意

给定 $k$ 个两两互质的正整数，求 $1 \sim n$ 中有多少数不能被任意一个数整除。

### 做法

「多少数不能被任意一个数整除」= $n - $ 「多少数能被任意一个数整除」。

考虑 DP。设 $f(n, k)$ 表示有多少个 $1 \sim n$ 的数，能被 $a_1,a_2\dots a_k$ 中的任意一个数整除。

很妙的转移！
$$
f(n, k) = \lfloor n / a_k\rfloor + f(n, k - 1) - f(\lfloor n / a_k\rfloor, k - 1)
$$
其中，$\lfloor n / a_k\rfloor$ 表示 $1 \sim n$ 中能被 $a_k$ 整除的数的个数，$f(n, k - 1)$ 表示 $1 \sim n$ 中能被 $a_1\dots a_{k-1}$ 整除的数的个数。

显然这两个集合可能有交，即 $1 \sim n$ 中既能被 $a_k$ 整除，又能被 $a_1 \dots a_{k-1}$ 中任意一个数整除的数。

如果一个数 $x$ 是这两个集合的交，那么 $\frac x{a_k}$ 一定能被 $a_1 \dots a_{k-1}$ 中任意一个数整除。那么 $\frac x{a_k}$ 的数量为 $f(\lfloor n / a_k\rfloor, k - 1)$。因为 $x$ 和 $\frac x{a_k}$ 一一对应，所以 $x$ 的数量也是 $f(\lfloor n / a_k\rfloor, k - 1)$。

直接用 (u)map 转移空间复杂度会爆。优化方案有两种：

> 方法一：整除分块。
>
> 前排提醒，这种做法在时间上被卡常乐【】
>
> 对于每一个有效的状态 $f(i, j)$，这个 $i$ 一定是由给定的 $n$ 开始，不断除以某个 $a_k$ 下取整得到的。根据 [知识](https://oi-wiki.org/math/number-theory/sqrt-decomposition/) 我们得知这样的 $i$ 的数量是根号级别的。
>
> 因此我们可以双指针得到 $n$ 除以某个数下取整可能的得到的值（如上所述，数量是根号级别的），将其离散化即可。
>
> 离散化后转移可以双指针，一个指向 $n$，一个指向 $\lfloor n / a_k\rfloor$。
>
> 而且这个状态的第二维可以滚动优化。空间复杂度做到了根号。
>
> 后排提醒，这种做法在时间上被卡常乐【】

> 方法二：暴力 + 记忆化。
>
> 我们设一个阈值 $B$，然后记忆化转移。对于状态 $f(i, j)$ 若 $i < B$ 则用数组记忆化。否则直接转移不记忆了。这里我取的 $B = 10^6$。不难（？）证明这样的复杂度是正确的。
>
> 极其相似的题有 [CF1806E](https://www.cnblogs.com/2huk/p/18194174#-cf1806e-tree-master)，比较相似的题有 [ABC365G](https://www.bilibili.com/video/BV1noiFeHEJi/?share_source=copy_web&vd_source=e1044e7a01b4b54d479c00e7fea3f47d&t=2716)。

正在渲染内容...