Oct 28, 2018

BZOJ 3817: Sum

题面

给定正整数 \(n, r\)，试求：

\[ \sum\limits_{d = 1}^{n} (-1)^{\left\lfloor \sqrt{d \cdot r \cdot d} \right\rfloor} \]

数据范围：\(n \le 10^9, \ r \le 10^4\)，测试数据组数 \(T \le 10^4\)。

题目链接：BZOJ 3817: Sum

分析

首先不难考虑到，如果 \(\sqrt{r}\) 是有理数（整数）的话，这个问题非常好解决：

  • 若 \(\sqrt{r}\) 为偶数，则原式答案显然为 \(n\)；
  • 若 \(\sqrt{r}\) 为奇数，则：
    • 若 \(n\) 为偶数，则 \(-1\) 与 \(1\) 个数相等，原式答案为 \(0\)；
    • 若 \(n\) 为奇数，则 \(-1\) 比 \(1\) 个数多一个，原式答案为 \(1\)；

接下来讨论 \(\sqrt{r}\) 是无理数的情况。我们不妨令 \(t = \sqrt{r}\)。

首先，显而易见地：

  • 若 \(\left\lfloor dt \right\rfloor\) 为偶数，则 \((-1)^{\left\lfloor dt \right\rfloor} = 1\)；
  • 若 \(\left\lfloor dt \right\rfloor\) 为奇数，则 \((-1)^{\left\lfloor dt \right\rfloor} = -1\)；

可以归纳出：

\[ (-1)^{\left\lfloor dt \right\rfloor} = 1 - 2\left( \left\lfloor dt \right\rfloor - 2\left\lfloor \frac{\left\lfloor dt \right\rfloor}{2} \right\rfloor \right) \]

那么：

\[ \begin{aligned} \sum\limits_{d = 1}^{n} (-1)^{\left\lfloor \sqrt{d \cdot r \cdot d} \right\rfloor} = & \sum\limits_{d = 1}^{n} \left[ 1 - 2\left( \left\lfloor dt \right\rfloor - 2\left\lfloor \frac{dt}{2} \right\rfloor \right) \right] \\ = & n - 2\sum\limits_{d = 1}^{n} \left\lfloor dt \right\rfloor + 4\sum\limits_{d = 1}^{n} \left\lfloor \frac{dt}{2} \right\rfloor \end{aligned} \]

至于为什么对于实数 \(n\) 有 \(\left\lfloor \frac{\left\lfloor n \right\rfloor}{2} \right\rfloor = \left\lfloor \frac{n}{2} \right\rfloor\)，简单想想就明白了，本文不再给出证明。

后两项均可记作 \(\sum\limits_{d = 1}^{n} \left\lfloor k \cdot d \right\rfloor\) 的形式，其中 \(k = \frac{at + b}{c}\)（\(a, b, c\) 均为整数，而 \(t = \sqrt{r}\) 是无理数）。这就显得跟类欧几里得可解决的问题很相似了。我们尝试仿照之前一篇博文 浅谈类欧几里德算法 里的推导方法对下面的式子进行推导（为了符合一般习惯下面一段中把 \(d\) 写作 \(i\)）：

\[ f(a, b, c, n) = \sum\limits_{i = 0}^{n} \left\lfloor i \cdot \frac{at + b}{c} \right\rfloor \]

令 \(k = \frac{at + b}{c}\)。

  • 若 \(k \ge1\)（即满足对所有 \(i\) 均有 \(\left\lfloor ki \right\rfloor > 0\)） ： \[ \begin{aligned} f(a, b, c, n) = & \sum\limits_{i = 0}^{n} \left\lfloor i \cdot \frac{at + b}{c} \right\rfloor \\ = & \sum\limits_{i = 0}^{n} \left\lfloor i \cdot ( \left\lfloor \frac{at + b}{c} \right\rfloor + \frac{at + b}{c} - \left\lfloor \frac{at + b}{c} \right\rfloor ) \right\rfloor \\ = & \left\lfloor \frac{at + b}{c} \right\rfloor \sum\limits_{i = 0}^{n} i + \sum\limits_{i = 0}^{n} \left\lfloor i \cdot \frac{at + b - c \left\lfloor \frac{at + b}{c} \right\rfloor}{c} \right\rfloor \\ = & \left\lfloor \frac{at + b}{c} \right\rfloor \frac{1}{2}n(n + 1) + f(a, b - c \left\lfloor \frac{at + b}{c} \right\rfloor, c, n) \end{aligned} \]

  • 若 \(k < 1\)（即不满足对所有 \(i\) 均有 \(\left\lfloor ki \right\rfloor > 0\)）：

\[ \begin{aligned} f(a, b, c, n) & = \sum\limits_{i = 0}^{n} \left\lfloor ki \right\rfloor \\ & = \sum\limits_{i = 0}^{n} \sum\limits_{j = 0}^{\left\lfloor ki \right\rfloor - 1} 1 \\ & = \sum\limits_{j = 0}^{\left\lfloor kn \right\rfloor - 1} \sum\limits_{i = 0}^{n} (j \le \left\lfloor ki \right\rfloor - 1) \\ & = \sum\limits_{j = 0}^{\left\lfloor kn \right\rfloor - 1} \sum\limits_{i = 0}^{n} (j < ki - 1) \\ & = \sum\limits_{j = 0}^{\left\lfloor kn \right\rfloor - 1} \sum\limits_{i = 0}^{n} (i > \frac{j + 1}{k}) \\ & = \sum\limits_{j = 0}^{\left\lfloor kn \right\rfloor - 1} (n - \left\lfloor \frac{j + 1}{k} \right\rfloor) \\ & \text{let } m = \left\lfloor kn \right\rfloor \\ & = \sum\limits_{j = 0}^{m - 1} (n - \left\lfloor \frac{j + 1}{k} \right\rfloor) \\ & = nm - \sum\limits_{j = 0}^{m - 1} \left\lfloor \frac{j + 1}{k} \right\rfloor \\ & = nm - \sum\limits_{j = 0}^{m - 1} \left\lfloor (j + 1) \cdot \frac{c}{at + b} \right\rfloor \\ & = nm - \sum\limits_{j = 0}^{m} \left\lfloor j \cdot \frac{c}{at + b} \right\rfloor \\ \end{aligned} \]

我们注意到最后一项已经比较类似于 \(f\) 式的定义，我们需要对其进行分母有理化：

\[ \begin{aligned} f(a, b, c, n) = & nm - \sum\limits_{j = 0}^{m} \left\lfloor j \cdot \frac{act - bc}{a^2t^2 - b^2} \right\rfloor \\ = & nm - f(ac, -bc, a^2t^2 - b^2, m) \end{aligned} \]

对其简要总结（令 \(m = \left\lfloor n \cdot \frac{at + b}{c} \right\rfloor\)）：

\[ f(a, b, c, n) = \begin{cases} \left\lfloor \frac{at + b}{c} \right\rfloor \frac{1}{2}n(n + 1) + f(a, b - c \left\lfloor \frac{at + b}{c} \right\rfloor, c, n) & \frac{at + b}{c} \ge 1 \\ nm - f(ac, -bc, a^2t^2 - b^2, m) & \frac{at + b}{c} < 1 \\ \end{cases} \]

就按照类欧的样子递归实现就好了。数学妙啊~ 复杂度为 \(\mathcal{O}(\log{n})\)。

为了防止中间过程爆 int64 需要在每一步的时候对 \(\frac{at + b}{c}\) 约分。但是由此一来复杂度就变成 \(\mathcal{O}(\log^2{n})\)了 QAQ… 最后附上 我的代码 以供参考。