P3579 [POI2014]PAN-Solar Panels 题解

TwoJie · 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 越小，那么这个约束条件就越容易满足。

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