分析
首先不难考虑到,如果 r 是有理数(整数)的话,这个问题非常好解决:
- 若 r 为偶数,则原式答案显然为 n;
- 若 r 为奇数,则:
- 若 n 为偶数,则 −1 与 1 个数相等,原式答案为 0;
- 若 n 为奇数,则 −1 比 1 个数多一个,原式答案为 1;
接下来讨论 r 是无理数的情况。我们不妨令 t=r。
首先,显而易见地:
- 若 ⌊dt⌋ 为偶数,则 (−1)⌊dt⌋=1;
- 若 ⌊dt⌋ 为奇数,则 (−1)⌊dt⌋=−1;
可以归纳出:
(−1)⌊dt⌋=1−2(⌊dt⌋−2⌊2⌊dt⌋⌋)
那么:
d=1∑n(−1)⌊d⋅r⋅d⌋==d=1∑n[1−2(⌊dt⌋−2⌊2dt⌋)]n−2d=1∑n⌊dt⌋+4d=1∑n⌊2dt⌋
至于为什么对于实数 n 有 ⌊2⌊n⌋⌋=⌊2n⌋,简单想想就明白了,本文不再给出证明。
后两项均可记作 d=1∑n⌊k⋅d⌋ 的形式,其中 k=cat+b(a,b,c 均为整数,而 t=r 是无理数)。这就显得跟类欧几里得可解决的问题很相似了。我们尝试仿照之前一篇博文 浅谈类欧几里德算法 里的推导方法对下面的式子进行推导(为了符合一般习惯下面一段中把 d 写作 i):
f(a,b,c,n)=i=0∑n⌊i⋅cat+b⌋
令 k=cat+b。
若 k≥1(即满足对所有 i 均有 ⌊ki⌋>0) :
f(a,b,c,n)====i=0∑n⌊i⋅cat+b⌋i=0∑n⌊i⋅(⌊cat+b⌋+cat+b−⌊cat+b⌋)⌋⌊cat+b⌋i=0∑ni+i=0∑n⌊i⋅cat+b−c⌊cat+b⌋⌋⌊cat+b⌋21n(n+1)+f(a,b−c⌊cat+b⌋,c,n)
若 k<1(即不满足对所有 i 均有 ⌊ki⌋>0):
f(a,b,c,n)=i=0∑n⌊ki⌋=i=0∑nj=0∑⌊ki⌋−11=j=0∑⌊kn⌋−1i=0∑n(j≤⌊ki⌋−1)=j=0∑⌊kn⌋−1i=0∑n(j<ki−1)=j=0∑⌊kn⌋−1i=0∑n(i>kj+1)=j=0∑⌊kn⌋−1(n−⌊kj+1⌋)let m=⌊kn⌋=j=0∑m−1(n−⌊kj+1⌋)=nm−j=0∑m−1⌊kj+1⌋=nm−j=0∑m−1⌊(j+1)⋅at+bc⌋=nm−j=0∑m⌊j⋅at+bc⌋
我们注意到最后一项已经比较类似于 f 式的定义,我们需要对其进行分母有理化:
f(a,b,c,n)==nm−j=0∑m⌊j⋅a2t2−b2act−bc⌋nm−f(ac,−bc,a2t2−b2,m)
对其简要总结(令 m=⌊n⋅cat+b⌋):
f(a,b,c,n)={⌊cat+b⌋21n(n+1)+f(a,b−c⌊cat+b⌋,c,n)nm−f(ac,−bc,a2t2−b2,m)cat+b≥1cat+b<1
就按照类欧的样子递归实现就好了。数学妙啊~ 复杂度为 O(logn)。
为了防止中间过程爆 int64
需要在每一步的时候对 cat+b 约分。但是由此一来复杂度就变成 O(log2n)了 QAQ… 最后附上 我的代码 以供参考。