关于高斯取整的那些事
dingziyang888
·
·
算法·理论
前言
本文由五年级的蒟蒻 dingziyang888 和 tangtianyao0123 共同编写，大佬们不喜勿喷。整体内容为高斯取整的拓展延申，整体难度偏高。
:::warning[建议]{open}
建议学习过数论组合 L2 的同学观看。
:::
定义与性质
本版块由 tangtianyao0123 编写。
定义
[x]$ 为不超过 $x$ 的最大整数，$\{x\} = x - [x]
性质
- 一个显然但容易忽略的是 [x] \in \Z
-
\left[ x \right ] \le x < \left[ x \right ] + 1$，$x - 1 <\left[ x \right ] \le x$，$0 \le \{x\} < 1
:::info[证明]{open}
$\therefore \left[x\right] \le x$\
$\because \left[x\right]$ 为不超过 $x$ 的最大整数\
$\therefore x < \left[x\right] + 1
2 移项，3 根据定义带入即可（我就不证了）
:::
- 若 n \in \Z，\left[n+x\right]=n+\left[x\right]，\left\{n+x\right\}=\left\{x\right\}（说人话就是取整内整数可以拿出来，取小内整数可以丢掉）。
:::info[提示]{open}
:::
4. 若 $a \le b$，则 $[a] \le [b]$。
:::info[证明]{open}
$[a] \le a \le b < [b] + 1$ 又 $\because [a], [b] \in \Z, [a] < [b]+1$\
$\therefore [a] \le [b]
:::
- 重要不等式：\{a+b\}\le\{a\}+\{b\}，[a+b]\ge[a]+[b]。
:::info[证明]{open}
$$\because 0\le\{a\},\{b\}$$
$$\therefore 0\le\{a\}+\{b\}$$
$$\therefore 0\le[\{a\}+\{b\}]$$
$$\therefore \{a+b\}=\{a\}+\{b\}-[\{a\}+\{b\}]\le\{a\}+\{b\}$$
第二个用 $[x] = x - \{x\}$ 即可
:::
7. 若 $n \in \Z \cap[1,∞)，x \in \R，[nx]\ge n[x]$。
:::info[证明]{open}
$[nx]=[n([x]+\{x\})]=[n[x]+n\{x\}]=n[x]+[n\{x\}]\ge n[x]
:::
- 设 x=\frac{a}{b}\in Q(\gcd(a,b)=1, b>0)，设 a/b=q...r，则 [x]=q，\{x\}=\frac{r}{b}。
:::info[证明]{open}
\because a/b=q...r
\therefore a=bq+r，0 \le r < b
\therefore x=\frac{bq+r}{b}=q+\frac{r}{b}
\because r<b
\therefore 0 \le \frac{r}{b} <1
\therefore [x]=q，\{x\}=\frac{r}{b}
:::
- 若 a,b,c\in [1,∞] \cap \Z，有 [\frac{[\frac{c}{a}]}{b}]=[\frac{c}{ab}]。
:::info[提示]{open}
根据 7 设带余除法即可
:::
取小的配对
本版块由 dingziyang888 编写。
基本知识
先说一个很容易理解的性质：\
若 a+b\in \mathbb{Z}，则 \{a\}+\{b\}=\begin{cases}
0 & (a,b \in \mathbb{Z})\\
1 & (a,b \notin \mathbb{Z})
\end{cases}，[a]+[b]=\begin{cases}
a+b & (a,b \in \mathbb{Z})\\
a+b-1 & (a,b \notin \mathbb{Z})
\end{cases}
这个性质很好理解：取小是整数说明要么都是零，要么小数部分相加抵消了，取整相加也是同理，有这个性质，就可以解决很多取整或取小符号内相加为整数的计算题了。
例题一
:::info[题目]{open}
计算：
\sum_{i=1}^{98}[\frac{14i}{33}]
:::
由刚刚介绍的性质，
\{\frac{14n}{33}\}+\{\frac{14(99-n)}{33}\}=
\begin{cases}
0 & \frac{14n}{33},\frac{14(99-n)}{33}\in\mathbb{Z}\\
1 & \frac{14n}{33},\frac{14(99-n)}{33}\notin\mathbb{Z}
\end{cases}
即
\{\frac{14n}{33}\}+\{\frac{14(99-n)}{33}\}=
\begin{cases}
0 & n=33,66\\
1 & n\ne33,66
\end{cases}
因为取整等于原数减去取小，所以原式等于取整内相加减去取小相加，而取小相加就用上面的方式配对，再乘 \frac{1}{2} 即可。
:::success[完整解答]{open}
解：
\because \frac{14n}{33}+\frac{14(99-n)}{33}=\frac{14\times99}{33}=42\in\mathbb{Z}
\begin{cases}
0 & \frac{14n}{33},\frac{14(99-n)}{33}\in\mathbb{Z}\\
1 & \frac{14n}{33},\frac{14(99-n)}{33}\notin\mathbb{Z}
\end{cases}
即
\begin{cases}
0 & n=33,66\\
1 & n\ne33,66
\end{cases}
故
\begin{align*}
\sum\_{n=1}^{98}{\frac{14n}{33}}&=\frac{1}{2}\cdot\sum\_{i=1}^{98}({\frac{14n}{33}}+{\frac{14(99-n)}{33}})\\&=\frac{1}{2}\times(98-2)\\&=48
\end{align*}
\begin{align*}
\therefore\sum_{i=1}^{98}[\frac{14i}{33}]&=\sum_{i=1}^{98}\frac{14i}{33}-\sum_{i=1}^{98}\{\frac{14i}{33}\}\\
&=\frac{14}{33}\cdot\sum_{i=1}^{98}i-\sum_{i=1}^{98}\{\frac{14i}{33}\}\\
&=\frac{14}{33}\times\frac{1}{2}\times(98+1)\times98-48\\
&=2010
\end{align*}
:::
接下来看一个一般化的题目。
例题二
:::info[题目]{open}
若正整数 m,n 满足 (m,n)=1，求证：
\sum_{i=1}^{m-1}[\frac{ni}{m}]=\sum_{j=1}^{n-1}[\frac{mj}{n}]
:::
以左式为例：
由刚刚讲的性质，有
\{\frac{ni}{m}\}+\{\frac{n(m-i)}{m}\}=1
代入左式即可。
:::success[完整解答]{open}
解：
\because \frac{ni}{m}+\frac{n(m-i)}{m}=\frac{nm}{m}=n\in\mathbb{Z}
又
\displaystyle\because(m,n)=1
且
\displaystyle i\nmid m
\therefore \{\frac{ni}{m}\}+\{\frac{n(m-i)}{m}\}=1
进而
LHS&=\sum_{i=1}^{m-1}\frac{ni}{m}-\sum_{i=1}^{m-1}\{\frac{ni}{m}\}\\
&=\frac{n}{m}\cdot\sum_{i=1}^{m-1}i-\frac{1}{2}\cdot\sum_{i=1}^{m-1}(\{\frac{ni}{m}\}+\{\frac{n(m-i)}{m}\}) \\
&=\frac{n}{m}\cdot\frac{1}{2}\cdot(m-1+1)\cdot(m-1)-\frac{1}{2}\cdot\sum_{i=1}^{m-1}1\\
&=\frac{1}{2}\cdot\frac{n}{m}\cdot m\cdot(m-1)-\frac{1}{2}\cdot(m-1)\\
&=\frac{1}{2}(m-1)(n-1)
\end{align*}
同理，
RHS=\frac{1}{2}(n-1)(m-1)
\therefore LHS=RHS
:::
### 例题三
:::info[题目]{open}
求
$$
\sum_{i=1}^{10}[\frac{250}{1+(\frac{i}{11-i})^4}]
$$
的值
:::
本题看起来不好化简，其实分子分母同乘小分数的分母后，**分子其实是一样的！！而且配对相加也为整数**，这题就好办了。
:::success[完整解答]{open}
解：对于 $1\le i\le 10$，有
$$
\begin{align*}
&\frac{250}{1+(\frac{i}{11-i})^4}+\frac{250}{1+(\frac{11-i}{i})^4}\\
&=\frac{250}{1+\frac{i^4}{(11-i)^4}}+\frac{250}{1+\frac{(11-i)^4}{i^4}}\\
&=\frac{250(11-i)^4}{(11-i)^4+i^4}+\frac{250i^4}{i^4+(11-i)^4}\\
&=\frac{250[(11-i)^4+i^4]}{(11-i)^4+i^4}\\
&=250\in\mathbb{Z}
\end{align*}
$$
又
$$\displaystyle (i^4+(11-i)^4,i^4)=1$$
且
$$\displaystyle n^4+(11-n)^4>6^4>250$$
$$\therefore n^4+(11-n)^4 \nmid 250n^4$$
$$\Rightarrow \frac{250n^4}{n^4+(11-n)^4}\notin\mathbb{Z}$$
$$\Rightarrow \{\frac{250}{1+(\frac{i}{11-i})^4}\}+\{\frac{250}{1+(\frac{11-i}{i})^4}\}=1$$
$$\therefore [\frac{250}{1+(\frac{i}{11-i})^4}]+[\frac{250}{1+(\frac{11-i}{i})^4}]=249$$
故
$$\sum_{i=1}^{10}[\frac{250}{1+(\frac{i}{11-i})^4}]=5\times249=1245$$
:::
## 埃尔米特恒等式
**本版块由 [tangtianyao0123](https://www.luogu.com.cn/user/1713700) 编写。**\
先做一个有数的证明：
### 例题一
:::info[题目]{open}
若实数 $a$ 满足
$$
\sum_{i=0}^{99}[a+\frac{i}{100}]=2023
$$
求 $[100a]$ 的值。
:::
简单放缩可知 $[a]$ 的范围，再假设 $100$ 个取整中有 $k$ 个 $[a]$，$100-k$ 个 $[a]+1$，解方程可知 $k$ 的值，回代即可。
:::success[完整解答]{open}
解：
$$
\because\sum_{i=0}^{99}[a+\frac{i}{100}]=2023
$$
$$
\therefore 100[a] \le 2023 < 100([a]+1)
$$
即
$$
[a] \le \frac{23}{100} < [a]+1
$$
由取整性质可知
$$
[a]=[\frac{23}{100}]=20
$$
又
$$
20=[a] < [a+\frac{1}{100}] \le [a+\frac{2}{100}] \le ... \le [a+\frac{99}{100}] \le [a]+1=21
$$
可设 $[a]$ 至 $[a+\frac{99}{100}]$ 中有 $k$ 个 $21$，$100-k$ 个 $20$，则
$$
21k+20(100-k)=2023
$$
解得
$$
k=23
$$
于是
$$
[a]=[a+\frac{1}{100}]=...=[a+\frac{76}{100}]=20,
$$
$$
[a+\frac{77}{100}]=[a+\frac{78}{100}]=...=a+[\frac{99}{100}]=21
$$
则
$$
a+\frac{76}{100} < 21 \le a+\frac{77}{100}
$$
$$
\Rightarrow 20\frac{23}{100} \le a < 20\frac{24}{100}
$$
$$
\Rightarrow 2023 \le 100a < 2024
$$
故
$$
[100a]=2023
$$
:::
接下来是埃尔米特恒等式的一般形式。
### 例题二
:::info[题目]{open}
(埃尔米特恒等式) 求证：
$$
\sum_{i=0}^{n-1}[a+\frac{i}{n}]=[na]。
$$
:::
同理，我们可以仿照上一题的做法。
:::success[完整解答]{open}
解：
不妨设
$$
\sum_{i=0}^{n-1}[a+\frac{i}{n}] = k
$$
$$
\therefore n[a]\le k<n([a]+1)
$$
$$
\therefore [a] \le \frac{k}{n} < [a]+1
$$
由取整性质可知
$$
[a] = [\frac{k}{n}]
$$
又
$$
[\frac{k}{n}]=[a]\le[a+\frac{1}{n}]\le[a+\frac{2}{n}]\le...\le[a+\frac{n-1}{n}]\le[a]+1=[\frac{k}{n}]+1
$$
不妨设
$$
[\frac{k}{n}]=[a]=[a+\frac{1}{n}]=[a+\frac{2}{n}]=...=[a+\frac{x}{n}],[a+\frac{x+1}{n}]=...=[a+\frac{n-1}{n}]=\frac{k}{n}+1
$$
$$
\therefore [\frac{k}{n}]\cdot (x+1)+([\frac{k}{n}]+1)\cdot (n-x-1)=k
$$
解得
$$
x=[\frac{k}{n}]\cdot n+n-k-1
$$
$$
\therefore a+\frac{[\frac{k}{n}]\cdot n+n-k-1}{n}<[\frac{k}{n}]+1\le a+\frac{[\frac{k}{n}]\cdot n+n-k}{n}
$$
即
$$
\frac{k}{n}\le a<\frac{k+1}{n}
$$
$$
\therefore k \le na<k+1
$$
$$
\therefore [na]=k=\sum_{i=0}^{n-1}[a+\frac{i}{n}]
$$
证毕
:::
### 例题三
:::info[题目]{open}
（$1986$ 年 IMO）求
$$
\sum_{i=1}^{+\infty}[\frac{x+2^{i-1}}{2^i}]
$$
的值
:::
不难发现 $[\frac{x+2^{i-1}}{2^i}]=[\frac{x}{2^i}+\frac{1}{2}]$ 根据刚刚的埃尔米特可以知道 $[a+\frac{1}{2}]=[2a]-[a]$ 最后展开抵消即可。
:::success[完整解答]{open}
解：
由例二，有 $[a]+[a+\frac{1}{2}]=[2a]$ 即 $[a+\frac{1}{2}]=[2a]-[a]$
$$
\therefore
\begin{align*}
\sum_{i=1}^{+\infty}[\frac{x+2^{i-1}}{2^i}]
&=\sum_{i=1}^{+\infty}[\frac{x}{2^i}+\frac{1}{2}]\\
&=\sum_{i=1}^{+\infty}([\frac{x}{2^{i-1}}]-[\frac{x}{2^i}])\\
&=[x]
\end{align*}
$$
:::
## 分子加一对于分数取整的影响
**本版块由 [dingziyang888](https://www.luogu.com.cn/user/1633534) 编写。**\
先上一个例题。
### 例题一
:::info[题目]{open}
如果正整数 $n$ 使得 $[\frac{n}{2}]+[\frac{n}{3}]+[\frac{n}{4}]+[\frac{n}{5}]+[\frac{n}{6}]=69$ 求 $n$ 的值。
:::
用 $x-1<[x]\le x$ 常规放缩可知 $n$ 的范围，加以枚举即可。
:::success[完整解答]{open}
解：
$$
\begin{align*}
\because LHS&\le\frac{n}{2}+\frac{n}{3}+\frac{n}{4}+\frac{n}{5}+\frac{n}{6}\\
&=n(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6})\\
&=\frac{29}{20}n
\end{align*}
$$
$$
\therefore \frac{29}{20}n\ge69\Rightarrow n\ge\frac{1380}{29}
$$
又
$$
\begin{align*}
LHS&\ge(\frac{n}{2}+\frac{n}{3}+\frac{n}{4}+\frac{n}{5}+\frac{n}{6})-5\\
&=n(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6})-5\\
&=\frac{29}{20}n-5\\
&=\frac{29n-100}{20}
\end{align*}
$$
$$
\therefore \frac{29n-100}{20}\le69\Rightarrow n\le\frac{1480}{29}
$$
于是
$$
\frac{1380}{29}\le n \le \frac{1480}{29}
$$
又
$$
n \in \mathbb{Z_+}
$$
$$
48 \le n \le 51
$$
经枚举，$n=48,49$。
:::
### 知识点
注意到，在例题一中，枚举出 $n=48$ 后判断 $n=49$ 是否成立时，没有必要带进原方程重新计算，由于 $49$ 不是 $2,3,4,5,6$ 的倍数，所以 $48$ 到 $49$ 除以 $2,3,4,5,6$ 取整的值不会改变，所以 $49$ 也满足方程。这一点也有很多应用。（证明见例题二引理）。
### 例题二
:::info[题目]{open}
已知 $x$ 为正整数，定义
$$
f(x)=\sum_{i=1}^{x}[\frac{x}{i}]
$$
（$1$）求 $f(2025)-f(2024)$ 的值\
（$2$）求最小正整数 $x$，使得 $f(x)-f(x-1)=12$
:::
由刚刚介绍的知识点，可知
$$
[\frac{2025}{i}] - [\frac{2024}{i}]=
\begin{cases}
1 & i \mid 2025\\
0 & i \nmid 2025
\end{cases}
$$
故原式即求 $2025$ 的因数个数（$d(2025)$）。
:::success[完整解答]{open}
解：引理：
$$
\forall 1 \le i \le x,
[\frac{x}{i}] - [\frac{x-1}{i}]=
\begin{cases}
1 & i \mid x\\
0 & i \nmid x
\end{cases}
$$
证明：
设
$$
x \div i = q ......r(0 \le r < i,r,q \in \mathbb{Z})
$$
分情况讨论：\
$\displaystyle 1^\circ$ 当 $r=0$ 时
$$
(x-1) \div i = (q-1)......(i-1)
$$
此时
$$
[\frac{x}{i}] - [\frac{x}{i}]=q-(q-1)=1
$$
$\displaystyle 2^\circ$ 当 $r \ne 0$ 时
$$
(x-1) \div i = q.....(r-1)
$$
此时
$$
[\frac{x}{i}] - [\frac{x}{i}]=q-q=0
$$
证毕。\
$(1)$ 由引理，
$$
[\frac{2025}{i}] - [\frac{2024}{i}]=
\begin{cases}
1 & i \mid 2025\\
0 & i \nmid 2025
\end{cases}
$$
且
$$
d(x)=(4+1) \times (2+1)=15
$$
故
$$
\begin{align*}
f(2025)-f(2024)&=\sum_{i=1}^{2025}[\frac{2025}{i}]-\sum_{i=1}^{2024}[\frac{2024}{i}]\\
&=\sum_{i=1}^{2025}[\frac{2025}{i}]-\sum_{i=1}^{2025}[\frac{2024}{i}]\\
&=\sum_{i=1}^{2025}([\frac{2025}{i}]-[\frac{2024}{i}])\\
&=d(2025)\\
&=15
\end{align*}
$$
$(2)$ 由引理，
$$
\forall 1 \le i \le x,
[\frac{x}{i}] - [\frac{x-1}{i}]=
\begin{cases}
1 & i \mid x\\
0 & i \nmid x
\end{cases}
$$
于是
$$
\begin{align*}
LHS&=\sum_{i=1}^{x}[\frac{x}{i}]-\sum_{i=1}^{x-1}[\frac{x-1}{i}]\\
&=\sum_{i=1}^{x}[\frac{x}{i}]-\sum_{i=1}^{x}[\frac{x-1}{i}]\\
&=\sum_{i=1}^{x}([\frac{x}{i}]-[\frac{x-1}{i}])\\
&=d(x)
\end{align*}
$$
故
$$
d(x)=12
$$
设质数 $p_1,p_2,p_3,...p_{+\infty}$，
考虑分情况：\
$\displaystyle 1^\circ$ 若 ${p_1}^{11}=x$，则 $x_{min}=2^{11}=2048$；\
$\displaystyle 2^\circ$ 若 ${p_1}\cdot{p_2}^5=x$，则 $x_{min}=3\times2^5=96$；\
$\displaystyle 3^\circ$ 若 ${p_1}^2\cdot{p_2}^3=x$，则 $x_{min}=3^2\times2^3=72$；\
$\displaystyle 4^\circ$ 若 $p_1\cdot p_2\cdot p_3^2=x$，则 $x_{min}=5\times3\times2^2=60$；
综上，$\displaystyle x_{min}=60$。
:::
:::info[拓展]{open}
由例题二，
$$
f(x)=f(x-1)+d(x)
$$
所以
$$
f(x)=\sum_{i=1}^{x}d(x)
$$
这一结论也会应用在例题三。
:::
### 例题三
:::info[题目]{open}
（2006IMO 预选）对于正整数 $n$ 定义：
$$
f(n)=\frac{1}{n}\sum_{i=1}^{n}[\frac{n}{i}]
$$
求证：\
（$1$）存在无穷多个 $n$，使得
$$
f(n+1)<f(n)
$$
（$2$）存在无穷多个 $n$，使得
$$
f(n+1)>f(n)
$$
:::
由例题二，有
$$
f(x)=\sum_{i=1}^{x}d(x)
$$
对于 $(1)$，可以先证一个引理：
$$
\forall n \ge 6,f(n)>2，
$$
有猜想：当 $n+1$ 取 $\ge 7$ 的质数时，$f(n+1)>f(n)$，放缩证明即可。\
对于 $(2)$：\
第一种方法：把满足条件的 $n$ 的数都设出来，证存在无穷多个；\
第二种方法：反证，只有有限个满足条件，证矛盾。\
**注意书写！！**
:::success[完整解答]{open}
证：引理 $1$：
$$
nf(n)-(n-1)f(n-1)=d(n)
$$
引理 $1$ 证明：
$$
\because nf(n)=\sum_{i=1}^{n}[\frac{n}{i}] ,
(n-1)f(n-1)=\sum_{i=1}^{n-1}[\frac{n-1}{i}]
$$
由例题二，
$$
\sum_{i=1}^{n}[\frac{n}{i}]-\sum_{i=1}^{n-1}[\frac{n-1}{i}]=d(n)
$$
即
$$
nf(n)-(n-1)f(n-1)=d(n)
$$
推论：
$$
f(n)=\sum_{i=1}^{n}d(i)
$$
$(1)$ 引理 $2$：当 $n\ge6$ 时，$f(n)>2$\
引理 $2$ 证明：
$$
\begin{align*}
f(n)&=\frac{1}{n}(\sum_{i=1}^{6}d(i)+\sum_{i=7}^{n-6}d(i))\\
&\ge\frac{1}{n}(1+2+2+3+2+4+2(n-6))\\
&=\frac{1}{n}(2n+2)
\end{align*}
$$
下证：当 $n+1$ 取 $\ge 7$ 的质数时，$f(n+1)>f(n)$ 证：
$$
\begin{align*}
f(n+1)&=\frac{1}{n+1}[nf(n)+d(n+1)]\\
&=\frac{1}{n+1}[nf(n)+2]\\
&<\frac{1}{n+1}[nf(n)+f(n)]\\
&=f(n)
\end{align*}
$$
证毕。\
$(2)$\
法一：
设数列 $n_k$ 满足 $f(n)>f(n - 1)$，令 $n_1=2$，有 $f(n_1)>f(n_1-1)$。\
若 $n_k$ 已找到，即
$$
\forall 1 \le i \le n_k-1,d(n_k)>d(i)
$$
考虑 $d(1)$ 至 $d(2n_k)$ 中有最大值，设第一次取到最大值的数为 $d(n_{k+1})$，则
$$
\forall 1 \le i \le n_{k+1}-1,d(n_{k+1})>d(i)
$$
且
$$
d(n_{k+1})>d(2n_k)>d(n_k)
$$
故找到无穷多个数 $\{n_k\}$ 使得
$$
\forall 1 \le i \le n_k-1,d(n_k)>d(i)
$$
于是
$$
f(n_{k}-1)=\frac{1}{n_{k}-1}\cdot\sum_{i=1}^{n_{k}-1}d(i)<d(n_k)
$$
$$
\begin{align*}
f(n_k)&=\frac{1}{n_k}[(n_{k}-1)f(n_{k}-1)+d(n_k)]\\
&>\frac{1}{n_k}[(n_{k}-1)f(n_{k}-1)+f(n_k-1)]\\
&=f(n_k-1)
\end{align*}
$$
证毕。
:::
## 后记
**原创不易，点个赞再走吧\~\~。**\
**求管理员通过 qwq。**