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}

数据范围

n109n \le 10^9

r104r \le 10^4

测试数据组数 T104T \le 10^4

题目链接

分析

首先不难考虑到,如果 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+bcf(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)\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) \
\end{aligned}

m=knm = \left\lfloor kn \right\rfloor,则有:

f(a,b,c,n)=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_{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}{a2t2 - b^2} \right\rfloor \
= & nm - f(ac, -bc, a2t2 - 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<1f(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, a2t2 - b^2, m) & \frac{at + b}{c} < 1 \
\end{cases}

就按照类欧的样子递归实现就好了。数学妙啊~

复杂度:O(logn)\mathcal{O}(\log{n})

实现

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

完整参考代码

%%%

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/10/28/bzoj-3817/