T1 - 洛谷保存站

### 题意

令 $y^2$ 是距离 $x$ 最近的完全平方数，若有不止一个最近的直接输出 $\texttt{Game Over}$ 结束程序。定义 $f(x) = (-1)^{y+1}y$。

求 $\sum_{i=l}^r f(i)$。$l, r \le 10^{18}$。

### 做法

$\texttt{Game Over}$ 是不可能的。

显然第一步差分。问题变成求 $[1, r]$ 的答案。

打表发现 $f(x)$ 中 $x$ 的系数形如：
$$
\begin{matrix}
x &: 1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20&\dots \\
(-1)^y&:[1&1]&[-1&-1&-1&-1]&[1&1&1&1&1&1]&[-1&-1&-1&-1&-1&-1&-1&-1]&\dots
\end{matrix}
$$
为了方便我们称一个极长连续段为一段，例如表中 $[7, 12]$ 就是一段。

不难发现：

- 第奇数段中的数都是 $1$，第偶数段中的数都是 $-1$。

- 第 $i$ 段的长度为 $2i$。

- $1 \sim n$ 段的长度和：
  $$
  \sum_{i=1}^n 2i = 2\sum_{i=1}^ni = n(n+1)
  $$

- 第 $n$ 段的左端点与右端点下标：

左端点相当于前 $1 \sim n - 1$ 段的长度和加一，右端点相当于 $1 \sim n$ 段的长度和。分别为：
  $$
  [n(n-1)+1,n(n+1)]
  $$

- 第 $n$ 段的下标和：

根据左右端点，用等差数列求和公式即可。
  $$
  \dfrac{2n \times (n(n-1)+1+n(n+1))}2 = 2n^3+n
  $$

- 前 $1 \sim n$ 段的答案（乘上了 $(-1)^{i+1}$ 的系数后的）：
  $$
  \sum_{i=1}^n(-1)^{i+1}(2n^3+n) = 2\times \sum_{i=1}^n(-1)^{i+1}i^3 + \sum_{i=1}^n(-1)^{i+1}i
  $$

所以我们可以计算 $r$ 之前有多少完整段，并用上面说的计算这些段的答案。对于剩下的一个不完整的段，等差数列直接算即可。

现在的问题是如何快速计算：
$$
\begin{matrix}\sum\limits_{i=1}^n(-1)^{i+1}i^3&\sum\limits_{i=1}^n(-1)^{i+1}i \end{matrix}
$$
后者是极易的。考虑计算前者：
$$
s_n = 1^3-2^3+3^3-4^3+\dots+(-1)^{n+1}i^3
$$
注意到：
$$
\begin{bmatrix}
s_{n-1} & n^3 & n^2 & i & 1
\end{bmatrix} \times \begin{bmatrix}
1 & 0 & 0 & 0 & 0 \\
1 & -1 & 0 & 0 & 0 \\
0 & -3 & -1 & 0 & 0 \\
0 & -3 & -2 & -1 & 0 \\
0 & -1 & -1 & -1 & -1
\end{bmatrix} =\begin{bmatrix}
s_n & -(n+1)^3 & -(n+1)^2 & -(n + 1) & -1
\end{bmatrix}
$$
矩阵加速即可。

正在渲染内容...