浅谈一类高斯求和问题

相信大家都知道高斯算法：首项加末项的和乘项数除以二等于等差数列的和。

实际应用中往往不会这么简单。一般需要根据等差数列的和，反过来求出等差数列的其它信息，此时对于边界的处理就很重要。

P1014 「NOIP1999PJ」Cantor 表

可以 \(O(N)\) 模拟，但太慢了。

先来看分子：\(1,1,2,3,2,1,1,2,3,4,\ldots\)

容易发现对于 \(1\to\infty\) 在 Z 字形中的每个层数 \(i\)，如果 \(i\bmod 2=0\)，那么就填入 \(1\to i\)，否则填入 \(i\to 1\)。

所以只要求出 \(\dfrac{(1+i)\times i}{2}<N\) 的最大的 \(i\)，就可以快速确定具体填的数。

\(O(\log N)\) 的二分不赘述，这里主要讨论 \(O(1)\) 的做法。

公式移项得到 \((1+i)\times i\)，取 \(i=\left\lfloor\sqrt{2N}\right\rfloor\) 时，结果可能小于也可能大于等于 \(2N\)，但一定是最接近的，因为算数平方根夹在 \(i\) 和 \(i+1\) 之间。额外判断一次即可。

分母除了填入方向相反别的完全相同。