PKUWC2025 D2T3 题解

考虑操作逆序，$+1,-1$ 互换，乘以 $k$ 变成整除 $k$。

考察什么样的数可以由 $l\sim r$ 做不超过 $B$ 次操作得到，可以发现只有在形如 $[\max(l/y-B,1),r/y+B]$ 这样的区间里的数可以被取到，其中 $y$ 是正整数。（这里不要求整除）

设这些区间的并为集合 $S$，可以发现集合 $S$ 有这样的性质：对于任意 $z\in S$，任意 $w \mid z$ 也满足 $w\in S$。证明就是考虑取出任意一个包含 $z$ 的区间 $[l/y-B,r/y+B]$，设 $z=aw$，那么 $w\in [l/(ay)-B,r/(ay)+B]$。

考虑分析集合 $S$ 的大小，对 $y$ 进行分类讨论。

对于 $y> \sqrt{r/B}$，我们有 $r/y+B<\sqrt{Br}+B$。

对于 $y\leq \sqrt{r/B}$，直接计算区间长度之和：

因此 $S$ 的大小是 $(r-l)\ln(r-l)+\sqrt{Br}$ 级别。

求出 $S$ 集合内的所有数可以直接暴力枚举小的 $y$，然后拼上 $\sqrt{Br}+B$ 内的所有数，因为区间关于 $y$ 单调所以去重是简单的。

求出 $S$ 集合后，考虑怎么做原问题。

因为这题做法是暴力，所以还是狄利克雷前缀和直接转移。

现在就有两个问题，一个是怎么求出所有刚好差了质数倍的转移对 $u,v$，另一个是分析总对数的级别。

考虑把 $S$ 集合分成两部分，把 $>\sqrt{Br}$ 的称为大集合，反之称为小集合。

小集合内的转移数显然不超过 $\sqrt{Br}\log\log r$，且容易求出，而大集合内每个数对应的 $y$ 都不超过 $\sqrt{r/B}$，因此它一定是 $[l-\sqrt{Br},r+\sqrt{Br}]$ 内某个数的因数。

因此我们只需对这个区间跑区间筛，然后只需要解决对于一个集合内的 $u$，定位 $u/p$ 在集合里的位置。

可以发现只需要知道 $u$ 所在区间的 $y$，并记录每个 $y$ 对应的区间左端点位置即可，复杂度应该是 $O(1)$ 的。

听说转移数可以分析出是 $|S|\log\log r$，但是我没学会。

这样的总复杂度就是 $O(B(\sqrt{Br}+(r-l)\ln (r-l))\log \log r)$，可以通过。

不过我赛时写的是对每个区间区间筛，还有一百万个 map 去重，这样居然也通过了。