BZOJ 3817: Sum

目录

题面

给定正整数 n,rn, r,试求:

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

数据范围n109, r104n \le 10^9, \ r \le 10^4,测试数据组数 T104T \le 10^4

题目链接BZOJ 3817: Sum

分析

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

  • r\sqrt{r} 为偶数,则原式答案显然为 nn
  • r\sqrt{r} 为奇数,则:
    • nn 为偶数,则 1-111 个数相等,原式答案为 00
    • nn 为奇数,则 1-111 个数多一个,原式答案为 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=12(dt2dt2) (-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)drd=d=1n[12(dt2dt2)]=n2d=1ndt+4d=1ndt2 \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}

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


后两项均可记作 d=1nkd\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=0niat+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}

  • k1k \ge1(即满足对所有 ii 均有 ki>0\left\lfloor ki \right\rfloor > 0) : f(a,b,c,n)=i=0niat+bc=i=0ni(at+bc+at+bcat+bc)=at+bci=0ni+i=0niat+bcat+bcc=at+bc12n(n+1)+f(a,bcat+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=0nki=i=0nj=0ki11=j=0kn1i=0n(jki1)=j=0kn1i=0n(j<ki1)=j=0kn1i=0n(i>j+1k)=j=0kn1(nj+1k)let m=kn=j=0m1(nj+1k)=nmj=0m1j+1k=nmj=0m1(j+1)cat+b=nmj=0mjcat+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)=nmj=0mjactbca2t2b2=nmf(ac,bc,a2t2b2,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=nat+bcm = \left\lfloor n \cdot \frac{at + b}{c} \right\rfloor):

f(a,b,c,n)={at+bc12n(n+1)+f(a,bcat+bc,c,n)at+bc1nmf(ac,bc,a2t2b2,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(logn)\mathcal{O}(\log{n})

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