自动搬运

查看原文

来自洛谷，原作者为

	TwoJie 菜是原罪

搬运于2025-08-24 21:50:22，当前版本为作者最后更新于2022-07-23 17:08:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一般的数论分块是求商相同的时候的区间贡献，然后就容易进入一种固定思维，就是我必须要统计完这个区间的所有信息，就会忽略一些题目本身的性质。

回到题目本身，首先可以发现一个性质（实际上这个性质是简化版的，我当时推出来的式子要复杂一点）：

如果区间 $(l,r]$ 存在 $x$ 的倍数，那么需要满足 $\lfloor \frac{l}{x} \rfloor < \lfloor \frac{r}{x} \rfloor$ 。

那么我们考虑枚举答案 $i$ ，对于答案 $i$ ，如果它满足上面的式子，那么这个 $i$ 就是合法的。

根据数论分块套路，我们可以改为枚举 $\frac{b}{i}$ 的商 $x$ ，那么这个 $x$ 必定对应着一个区间，而我们想要答案尽量大，就会想要取这个区间最大的那个，也就是 $x$ 尽量大。

代回上面那个约束条件，我们发现因为是枚举商，所以 $\lfloor \frac{r}{x} \rfloor$ 的值是不变的，我们再看左边的那个式子，发现 $x$ 越大， $\lfloor \frac{l}{x} \rfloor$ 越小，那么这个约束条件就越容易满足。

实际上这就是这道题隐藏的贪心性质，发现之后就简单了。