ARC135E

· · 题解

打表，发现最后一段是等差数列，于是差分一下。

差分后，发现大约在 \sqrt x 项后，数列全部相等。观察相等前的几项，仍然是等差数列，考虑再差分一次。

差分后，发现数列只有大约 \sqrt[3]x 段。重新观察一阶差分，发现等差数列一直持续到即将变得小于 0，我们可以据此算出二阶差分相同的一段数的长度。可以利用二次函数求和的方法 O(1) 地计算二阶差分相同的一段对应的原数列的和。

时间复杂度 O(T\sqrt[3]x)。