关键概念性质

不等式去掉取整符号

对于实数 xx 和整数 nn，有些时候我们可以去掉取整符号：

  1. x<n⇔⌊x⌋<nx<n\Leftrightarrow \lfloor x\rfloor <n；
  2. x>n⇔⌈x⌉>nx>n\Leftrightarrow \lceil x\rceil>n；
  3. x≤n⇔⌈x⌉≤nx\le n\Leftrightarrow \lceil x\rceil\le n；
  4. x≥n⇔⌊x⌋≥nx\ge n\Leftrightarrow \lfloor x\rfloor\ge n。

这些不等式的证明，我们只需要考虑 xx 在 n−1,n,n+1n-1,n,n+1 这些点之间的情况即可，容易验证。

函数自变量加取整符号

若 f(x)f(x) 是连续并且单调递增的，并且如果 f(x)∈Zf(x)\in \mathbb Z 可以推出 x∈Zx\in \mathbb Z，那么我们就有：

  1. ⌊f(x)⌋=⌊f(⌊x⌋)⌋\lfloor f(x)\rfloor=\lfloor f(\lfloor x\rfloor)\rfloor；
  2. ⌈f(x)⌉=⌈f(⌈x⌉)⌉\lceil f(x)\rceil=\lceil f(\lceil x\rceil)\rceil。

如果 xx 是整数，那么这个等式显然成立，接下来我们考虑 xx 不是整数。

我们首先证明第一条，由于 ⌊x⌋<x\lfloor x\rfloor< x，那么 f(⌊x⌋)≤f(x)f(\lfloor x\rfloor)\le f(x)，于是我们有 ⌊f(⌊x⌋)⌋≤⌊f(x)⌋\lfloor f(\lfloor x\rfloor)\rfloor\le \lfloor f(x)\rfloor。

假设 ⌊f(⌊x⌋)⌋<⌊f(x)⌋\lfloor f(\lfloor x\rfloor)\rfloor <\lfloor f(x)\rfloor，由不等式的性质，我们可以得到 f(⌊x⌋)<⌊f(x)⌋f(\lfloor x\rfloor)<\lfloor f(x)\rfloor。

由于 f(x)∈Zf(x)\in \mathbb Z 可以推出 x∈Zx\in \mathbb Z，所以 f(x)≠⌊f(x)⌋f(x)\neq \lfloor f(x)\rfloor，所以 f(x)>⌊f(x)⌋f(x)>\lfloor f(x)\rfloor。

因此我们得到了 f(⌊x⌋)f(\lfloor x\rfloor) 与 f(x)f(x) 之间夹了一个整数，由于 f(x)f(x) 是连续的，所以一定存在一个 ⌊x⌋<y<x\lfloor x\rfloor <y<x 使得 f(y)=⌊f(x)⌋f(y)=\lfloor f(x)\rfloor。

此时可以推出 yy 是整数，然而 ⌊x⌋\lfloor x\rfloor 与 xx 之间并不存在整数，所以假设不成立，因此 ⌊f(⌊x⌋)⌋=⌊f(x)⌋\lfloor f(\lfloor x\rfloor)\rfloor =\lfloor f(x)\rfloor。

第二条的证明过程同上。

区间整数点数量

对于下面三种类型的区间，如果有 α≤β\alpha\le \beta，我们可以用给不等式加取整符号的方法，求出区间内的整数点数量。

  1. 对区间 [α,β][\alpha,\beta] 来说，α≤n≤β\alpha\le n\le \beta 会有 ⌈α⌉≤n≤⌊β⌋\lceil\alpha\rceil \le n\le\lfloor\beta\rfloor，于是数量是 ⌊β⌋−⌈α⌉+1\lfloor\beta\rfloor-\lceil\alpha\rceil+1；
  2. 对区间 [α,β)[\alpha,\beta) 来说，α≤n<β\alpha\le n\lt \beta 会有 ⌈α⌉≤n<⌈β⌉\lceil\alpha\rceil\le n<\lceil\beta\rceil，于是数量是 ⌈β⌉−⌈α⌉\lceil\beta\rceil-\lceil\alpha\rceil；
  3. 对区间 (α,β](\alpha,\beta] 来说，α<n≤β\alpha<n\le \beta 会有 ⌊α⌋<n≤⌊β⌋\lfloor\alpha\rfloor<n\le \lfloor\beta\rfloor，于是数量是 ⌊β⌋−⌊α⌋\lfloor\beta\rfloor-\lfloor\alpha\rfloor；

对这三种情况，如果对应区间之内确实至少存在一个整数，那么由于这个不等式转化是充要的，所以它给出的答案一定也是正确的，所以我们只需要确定，当对应区间不存在整数时，公式给出的答案是不是 00。

  1. 对区间 [α,β][\alpha,\beta] 来说，α=n+ε1,β=n+ε2,0<ε1≤ε2<1\alpha=n+\varepsilon_1,\beta=n+\varepsilon_2,0\lt\varepsilon_1\le\varepsilon_2\lt1；
  2. 对区间 [α,β)[\alpha,\beta) 来说，α=n+ε1,β=n+ε2,0<ε1≤ε2≤1\alpha=n+\varepsilon_1,\beta=n+\varepsilon_2,0\lt \varepsilon_1\le\varepsilon_2\le 1；
  3. 对区间 (α,β](\alpha,\beta] 来说，α=n+ε1,β=n+ε2,0≤ε1≤ε2<1\alpha=n+\varepsilon_1,\beta=n+\varepsilon_2,0\le \varepsilon_1\le\varepsilon_2\lt 1；

这些情况就是所有答案应当为 00 的情况，可以验证对应公式给出的都是 00，因此这个公式是正确的。

推论

  1. 对于 f(x)=xf(x)=\sqrt x 符合要求，有 ⌊x⌋=⌊⌊x⌋⌋\lfloor\sqrt{x}\rfloor=\lfloor \sqrt{\lfloor x\rfloor}\rfloor。

  2. 对于 f(x)=x+mnf(x)=\cfrac{x+m}{n} 符合要求，有 ⌊⌊x⌋+mn⌋=⌊x+mn⌋\lfloor\cfrac{\lfloor x\rfloor +m}{n}\rfloor=\lfloor\cfrac{x+m}{n}\rfloor。

    特别地，令 m=0m=0，我们就有 ⌊xkn⌋=⌊⌊x/k⌋n⌋\lfloor\cfrac{x}{kn}\rfloor=\lfloor\frac{\lfloor x/k\rfloor}{n}\rfloor。

例题

例1

求 ∑n=1N[⌊n3⌋∣n]\sum_{n=1}^N[\lfloor\sqrt[3]{n}\rfloor\mid n]。

设 K=⌊N3⌋K=\lfloor\sqrt[3]{N}\rfloor，枚举 k=⌊n3⌋k=\lfloor\sqrt[3]{n}\rfloor，当 k<Kk<K 时，符合条件的 n≤Nn\le N；当 k=Kk=K 时，符合条件的 nn 可能会超过 NN。

因此，我们有：

∑n=1N[⌊n3⌋∣n]=∑n=1K3−1[⌊n3⌋∣n]+∑n=K3N[K∣n]=∑n,k[k=⌊n3⌋][k∣n][1≤n<K3]+∑n,m[n=Km][K3≤n≤N]=∑n,k,m[k≤n3<k+1][n=km][1≤n<K3]+∑m[K3≤Km≤N]=∑n,k,m[k≤n3<k+1][n=km][1≤k<K]+⌊NK⌋−K2+1=∑k,m[k3≤km<(k+1)3][1≤k<K]+⌊NK⌋−K2+1=∑k,m[k2≤m<(k+1)3k][1≤k<K]+⌊NK⌋−K2+1=∑k=1K−1(3k+4)+⌊NK⌋−K2+1=7+3K+12(K−1)+⌊NK⌋−K2+1=⌊NK⌋+12K2+52K−3\begin{aligned} \sum_{n=1}^N [\lfloor\sqrt[3]{n}\rfloor\mid n] &=\sum_{n=1}^{K^3-1}[\lfloor\sqrt[3]{n}\rfloor\mid n]+\sum_{n=K^3}^N [K\mid n]\\ &=\sum_{n,k}[k=\lfloor\sqrt[3]{n}\rfloor][k\mid n][1\le n<K^3]+\sum_{n,m}[n=Km][K^3\le n\le N]\\ &=\sum_{n,k,m}[k\le \sqrt[3]{n}<k+1][n=km][1\le n<K^3]+\sum_{m}[K^3\le Km\le N]\\ &=\sum_{n,k,m}[k\le \sqrt[3]{n}<k+1][n=km][1\le k<K]+\lfloor\frac{N}{K}\rfloor-K^2+1\\ &=\sum_{k,m}[k^3\le km<(k+1)^3][1\le k<K]+\lfloor\frac{N}{K}\rfloor-K^2+1\\ &=\sum_{k,m}[k^2\le m<\frac{(k+1)^3}{k}][1\le k<K]+\lfloor\frac{N}{K}\rfloor-K^2+1\\ &=\sum_{k=1}^{K-1}(3k+4)+\lfloor\frac{N}{K}\rfloor-K^2+1\\ &=\frac{7+3K+1}{2}(K-1)+\lfloor\frac{N}{K}\rfloor-K^2+1\\ &=\lfloor\frac{N}{K}\rfloor+\frac{1}{2}K^2+\frac{5}{2}K-3 \end{aligned}

注意，中间把 1≤n<K31\le n<K^3 换成 1≤k<K1\le k<K 这一步比较关键，这是因为我们固定 kk 后遍历符合条件的 nn，仍然可以遍历到 [1,K3)[1,K^3) 之间的所有 nn。

其次，我们写 ∑n,k,m\sum_{n,k,m} 的意思是 n,k,mn,k,m 分别独立地遍历所有非负整数。

例2

求 ∑1≤k<n⌊k⌋\sum_{1\le k<n}\lfloor\sqrt{k}\rfloor。

同样地设 a=⌊n⌋a=\lfloor\sqrt{n}\rfloor，那么：

∑1≤k<n⌊k⌋=∑m,km[m=⌊k⌋][k<a2]+∑a2≤k<n⌊k⌋=∑m,km[m≤k<m+1][k<a2]+(n−a2)a=∑m,km[m2≤k<(m+1)2][m<a]+(n−a2)a=∑mm(2m+1)[m<a]+(n−a2)a=∑m(2m2‾+3m1‾)[m<a]+(n−a2)a=23a3‾+32a2‾+(n−a2)a=na−13a3−12a2−16a\begin{aligned} \sum_{1\le k<n}\lfloor\sqrt{k}\rfloor&=\sum_{m,k}m[m=\lfloor\sqrt{k}\rfloor][k<a^2]+\sum_{a^2\le k<n}\lfloor\sqrt{k}\rfloor\\ &=\sum_{m,k}m[m\le\sqrt{k}<m+1][k<a^2]+(n-a^2)a\\ &=\sum_{m,k}m[m^2\le k<(m+1)^2][m<a]+(n-a^2)a\\ &=\sum_{m}m(2m+1)[m<a]+(n-a^2)a\\ &=\sum_{m}(2m^{\underline{2}}+3m^{\underline{1}})[m<a]+(n-a^2)a\\ &=\frac{2}{3}a^{\underline{3}}+\frac{3}{2}a^{\underline{2}}+(n-a^2)a\\ &=na-\frac{1}{3}a^3-\frac{1}{2}a^2-\frac{1}{6}a \end{aligned}

其中 xn‾x^{\underline{n}} 代表 nn 次下降幂，我们有 xn‾=(x+1)n+1‾−xn+1‾n+1x^{\underline{n}}=\cfrac{(x+1)^{\underline{n+1}}-x^{\underline{n+1}}}{n+1}，这个形式及其有利于求和。

例3

证明：n=∑k=0m−1⌈n−km⌉n=\sum_{k=0}^{m-1}\lceil\cfrac{n-k}{m}\rceil，当 n≥mn\ge m 且 n,mn,m 为正整数。

不妨做带余除法 n=qm+rn=qm+r，对 kk 分类讨论：

  1. 当 k≤r−1k\le r-1 时，有 ⌈n−km⌉=q+1\lceil\cfrac{n-k}{m}\rceil=q+1；
  2. 当 r≤k≤m−1r\le k\le m-1 时，我们有 (q−1)m+1≤qm+r−m+1≤qm+r−k≤qm(q-1)m+1\le qm+r-m+1\le qm+r-k\le qm，因此 ⌈n−km⌉=q\lceil\cfrac{n-k}{m}\rceil=q。

所以，右边的和式就是 (q+1)r+q(m−r)=qm+r=n(q+1)r+q(m-r)=qm+r=n。

根据 ⌈nm⌉=⌊n+m−1m⌋\lceil\cfrac{n}{m}\rceil=\lfloor\cfrac{n+m-1}{m}\rfloor，可以得到 n=∑k=0m−1⌊n+km⌋n=\sum_{k=0}^{m-1}\lfloor\cfrac{n+k}{m}\rfloor。

我们令 n=⌊mx⌋n=\lfloor mx\rfloor，可以得到 ⌊mx⌋=∑k=0m−1⌊⌊mx⌋+km⌋=∑k=0m−1⌊x+km⌋\lfloor mx\rfloor=\sum_{k=0}^{m-1}\lfloor\cfrac{\lfloor mx\rfloor +k}{m}\rfloor=\sum_{k=0}^{m-1}\lfloor x+\cfrac{k}{m}\rfloor。

例4

求 ∑1<k<22n12⌊lg⁡k⌋4⌊lg⁡lg⁡k⌋\sum_{1<k<2^{2^n}}\cfrac{1}{2^{\lfloor \lg k\rfloor}4^{\lfloor\lg\lg k\rfloor}}。

注意这里的 lg⁡\lg 底数是 22。

由于 lg⁡x∈Z\lg x\in\mathbb Z 可以推出 x∈Zx\in\mathbb Z，因此 ⌊lg⁡x⌋=⌊lg⁡⌊x⌋⌋\lfloor\lg x\rfloor=\lfloor \lg \lfloor x\rfloor\rfloor。

∑1<k<22n12⌊lg⁡k⌋4⌊lg⁡lg⁡k⌋=∑1<k<22n12⌊lg⁡k⌋4⌊lg⁡⌊lg⁡k⌋⌋=∑k,m12m4⌊lg⁡m⌋[m=⌊lg⁡k⌋][1<k<22n]=∑k,m12m4⌊lg⁡m⌋[m≤lg⁡k<m+1][1≤m<2n]=∑k,m12m4⌊lg⁡m⌋[2m≤k<2m+1][1≤m<2n]=∑m2m+1−2m2m4⌊lg⁡m⌋[1≤m<2n]=∑m14⌊lg⁡m⌋[1≤m<2n]=∑m,p14p[p=⌊lg⁡m⌋][1≤m<2n]=∑m,p14p[2p≤m<2p+1][0≤p<n]=∑p2p+1−2p4p[0≤p<n]=∑p12p[0≤p<n]=2−12n−1\begin{aligned} \sum_{1<k<2^{2^n}}\cfrac{1}{2^{\lfloor \lg k\rfloor}4^{\lfloor\lg\lg k\rfloor}}&=\sum_{1<k<2^{2^n}}\cfrac{1}{2^{\lfloor \lg k\rfloor}4^{\lfloor\lg\lfloor\lg k\rfloor\rfloor}}\\ &=\sum_{k,m}\frac{1}{2^m 4^{\lfloor \lg m\rfloor}}[m=\lfloor\lg k\rfloor][1<k<2^{2^n}]\\ &=\sum_{k,m}\frac{1}{2^m4^{\lfloor\lg m\rfloor}}[m\le \lg k<m+1][1\le m<2^n]\\ &=\sum_{k,m}\frac{1}{2^m4^{\lfloor\lg m\rfloor}}[2^m\le k<2^{m+1}][1\le m<2^n]\\ &=\sum_{m}\frac{2^{m+1}-2^m}{2^m4^{\lfloor\lg m\rfloor}}[1\le m<2^n]\\ &=\sum_{m}\frac{1}{4^{\lfloor\lg m\rfloor}}[1\le m<2^n]\\ &=\sum_{m,p}\frac{1}{4^p}[p=\lfloor\lg m\rfloor][1\le m<2^n]\\ &=\sum_{m,p}\frac{1}{4^p}[2^p\le m<2^{p+1}][0\le p<n]\\ &=\sum_{p}\frac{2^{p+1}-2^p}{4^p}[0\le p<n]\\ &=\sum_{p}\frac{1}{2^p}[0\le p<n]\\ &=2-\frac{1}{2^{n-1}} \end{aligned}