题解：P17239 『STA - R10』雨落玫瑰

sbno333 · 2026-08-11 21:20:40 · 题解

看到这个题的一瞬间就知道这是类欧题，想了一会发现是板子。

直接做不好做，尝试简单分析一下。

我们考虑 \frac{a}{c} 和 \frac{d}{f} 的关系会影响结果，具体如果差距较大，在 i 很大的时候变为一定贡献或者不贡献。

根据这个，考虑什么时候成立。

当 \frac{ai+b}{c}\le\frac{di+e}{f} 的时候，下取整后也一定是对的，于是我们必然要贡献。满足这个条件形如一段前缀或者后缀，算完之后类欧即可。

当 \frac{ai+b}{c}>\frac{di+e}{f}+1 的时候，显然下取整救不动，所以不贡献。

当 \frac{di+e}{f}\le\frac{ai+b}{c}\le\frac{di+e}{f}+1，显然下取整后二者只相差一，而且 i 形如一个区间。此刻我们可以做很多事情。

设 x=\lfloor \frac{ai+b}{c}\rfloor，y=\lfloor \frac{di+e}{f}\rfloor。

我们有 y\le x\le y+1，我们希望计算对于 x=y 时，x 的和。

我们考虑计算多少个 x=y，就是总数减去多少个 x=y+1，也就是总数减去 \sum x-\sum y。

我们此时多了个 x，于是考虑在这个式子也多个 x，变为 \sum x^2-\sum y^2。

当 x=y 时，x^2-y^2=0。

否则 x^2-y^2=2y+1。