Oct 28, 2018

BZOJ 3817: Sum

目录

题面

给定正整数 n,rn, r，试求：

∑d=1n(−1)⌊d⋅r⋅d⌋ \sum\limits_{d = 1}^{n} (-1)^{\left\lfloor \sqrt{d \cdot r \cdot d} \right\rfloor}

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

题目链接：BZOJ 3817: Sum

分析

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

  • 若 r\sqrt{r} 为偶数，则原式答案显然为 nn；
  • 若 r\sqrt{r} 为奇数，则：
    • 若 nn 为偶数，则 −1-1 与 11 个数相等，原式答案为 00；
    • 若 nn 为奇数，则 −1-1 比 11 个数多一个，原式答案为 11；

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

首先，显而易见地：

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

可以归纳出：

(−1)⌊dt⌋=1−2(⌊dt⌋−2⌊⌊dt⌋2⌋) (-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)

那么：

∑d=1n(−1)⌊d⋅r⋅d⌋=∑d=1n[1−2(⌊dt⌋−2⌊dt2⌋)]=n−2∑d=1n⌊dt⌋+4∑d=1n⌊dt2⌋ \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}

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

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

f(a,b,c,n)=∑i=0n⌊i⋅at+bc⌋ f(a, b, c, n) = \sum\limits_{i = 0}^{n} \left\lfloor i \cdot \frac{at + b}{c} \right\rfloor

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

  • 若 k≥1k \ge1（即满足对所有 ii 均有 ⌊ki⌋>0\left\lfloor ki \right\rfloor > 0） ： f(a,b,c,n)=∑i=0n⌊i⋅at+bc⌋=∑i=0n⌊i⋅(⌊at+bc⌋+at+bc−⌊at+bc⌋)⌋=⌊at+bc⌋∑i=0ni+∑i=0n⌊i⋅at+b−c⌊at+bc⌋c⌋=⌊at+bc⌋12n(n+1)+f(a,b−c⌊at+bc⌋,c,n) \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<1k < 1（即不满足对所有 ii 均有 ⌊ki⌋>0\left\lfloor ki \right\rfloor > 0）：

f(a,b,c,n)=∑i=0n⌊ki⌋=∑i=0n∑j=0⌊ki⌋−11=∑j=0⌊kn⌋−1∑i=0n(j≤⌊ki⌋−1)=∑j=0⌊kn⌋−1∑i=0n(j<ki−1)=∑j=0⌊kn⌋−1∑i=0n(i>j+1k)=∑j=0⌊kn⌋−1(n−⌊j+1k⌋)let m=⌊kn⌋=∑j=0m−1(n−⌊j+1k⌋)=nm−∑j=0m−1⌊j+1k⌋=nm−∑j=0m−1⌊(j+1)⋅cat+b⌋=nm−∑j=0m⌊j⋅cat+b⌋ \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}

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

f(a,b,c,n)=nm−∑j=0m⌊j⋅act−bca2t2−b2⌋=nm−f(ac,−bc,a2t2−b2,m) \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=⌊n⋅at+bc⌋m = \left\lfloor n \cdot \frac{at + b}{c} \right\rfloor）：

f(a,b,c,n)={⌊at+bc⌋12n(n+1)+f(a,b−c⌊at+bc⌋,c,n)at+bc≥1nm−f(ac,−bc,a2t2−b2,m)at+bc<1 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}

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

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