6029

注意到相邻两数的向下取整的差值不可能大于 $1$，也就是： $$ \lfloor \frac x k\rfloor-\lfloor \frac {x-1} k\rfloor \leq 1 $$ 稍微推广一下，我们得到： $$ x-1-\lfloor \frac {x-1} k\rfloor \leq... ......

[传送门](https://loj.ac/p/6029) ``` #include using ll = long long; const int N = 1e5 + 10; const int MOD = 1e9 + 7; const ll INF = 0x3f3f3f3f3f3f3f3f * 2 ......

#6029. 「雅礼集训 2017 Day1」市场 题目描述 数据范围1e5 题解 对于这种数据貌似可以快速缩小的题目，我们可以用势能分析来证明其某暴力或者什么做法的复杂度。 设某节点的势能函数是点内数的极差，每次除一个数极差一定会减半，总共会被除 $\log$ 次。 然而有特殊情况，如果考虑下取整 ......