zsh

Formulas

定义取整函数：

$$\begin{aligned} \lfloor x \rfloor &= 小于或等于x的最大整数 \\ \lceil x \rceil &= 大于或等于x的最小整数 \end{aligned} \tag{3.1} \label{3.1}$$

基本性质：

$$\lceil x \rceil - \lfloor x \rfloor = [x不是整数] \tag{3.2} \label{3.2}$$ $$x-1 < \lfloor x \rfloor \le x \le \lceil x \rceil x < x+1 \tag{3.3} \label{3.3}$$ $$\begin{aligned} \lfloor -x \rfloor &= - \lceil x \rceil \\ \lceil -x \rceil &= -\lfloor x \rfloor \end{aligned} \tag{3.4} \label{3.4}$$ $$\begin{aligned} \lfloor x \rfloor = n &\Leftrightarrow n \le x \lt n+1, &(a)\\ \lfloor x \rfloor = n &\Leftrightarrow x-1 \lt n \le x, &(b)\\ \lceil x \rceil = n &\Leftrightarrow n-1 \lt x \le n, &(c)\\ \lceil x \rceil = n &\Leftrightarrow x \le n \lt x+1, &(d) \end{aligned} \tag{3.5} \label{3.5}$$

以下$x$表示实数， $n$表示整数。有：

$$\lfloor x + n \rfloor = \lfloor x \rfloor + n \tag{3.6} \label{3.6}$$ $$\begin{aligned} x \lt n &\Leftrightarrow \lfloor x \rfloor \lt n, &(a) \\ n \lt x &\Leftrightarrow n \lt \lceil x \rceil, &(b) \\ x \le n &\Leftrightarrow \lceil x \rceil \le n, &(c) \\ n \le x &\Leftrightarrow n \le \lfloor x \rfloor, &(d) \end{aligned} \tag{3.7} \label{3.7}$$

定义分数部分：

$$\{x\} = x - \lfloor x \rfloor. \tag{3.8} \label{3.8}$$

=== 底和顶的应用 ===

$$\lfloor \sqrt{\lfloor x \rfloor } \rfloor = \lfloor \sqrt x \rfloor,\quad x\ge 0 \label{3.9} \tag{3.9}$$

若函数$f(x)$满足性质：在实数区间连续+单调递增，并且有$f(x)=整数 \Rightarrow x=整数$，则有性质：

$$\begin{aligned} \lfloor f(x) \rfloor = \lfloor f(\lfloor x \rfloor) \rfloor \\ \lceil f(x) \rceil = \lceil f(\lceil x \rceil) \rceil \end{aligned} \tag{3.10} \label{3.10}$$

\eqref{3.10}的一个特例：
当$m为整数，n为正整数$，有：

$$\begin{aligned} \left\lfloor {x+m \over n} \right\rfloor &= \left\lfloor {\lfloor x \rfloor + m \over n}\right\rfloor \\ \left\lceil {x+m \over n} \right\rceil &= \left\lceil {\lceil x \rceil + m \over n}\right\rceil \\ \end{aligned} \tag{3.11} \label{3.11}$$

区间中有多少个整数？

$$\begin{array}{clc} 区间 & 包含的整数 & 限制条件\\ \hline [\alpha \dots \beta] & \lfloor \beta \rfloor - \lceil \alpha \rceil + 1 & \alpha \le \beta \\ [\alpha \dots \beta) & \lceil \beta \rceil- \lceil \alpha \rceil & \alpha \le \beta \\ (\alpha \dots \beta] & \lfloor \beta \rfloor - \lfloor \alpha \rfloor & \alpha \le \beta \\ (\alpha \dots \beta) & \lceil \beta \rceil - \lfloor \alpha \rfloor - 1 & \alpha \lt \beta \end{array} \tag{3.12} \label{3.12}$$

谱的内容没讲。

底和顶的递归式

高徳纳数：

$$\begin{aligned} K_0 &= 1; \\ K_{n+1} &= 1 + \min(2K_{\lfloor \frac n 2 \rfloor}, 3K_{\lfloor \frac n 3 \rfloor}),\quad n\ge 0 \end{aligned} \tag{3.16} \label{3.16}$$

最常用的关系式：

$$n = \lceil n/2 \rceil + \lfloor n/2 \rfloor \tag{3.17} \label{3.17}$$

MOD

定义mod：

$$x\mod y = x - y \lfloor x/y \rfloor, \quad y\ne 0 \tag{3.21} \label{3.21}$$

其中$y$为模

有性质：

$$\begin{aligned} 0 \le x \mod y \lt y, &\quad y \gt 0; \\ 0 \ge x \mod y \gt y, &\quad y \lt 0. \end{aligned}$$

约定：

$$x \mod 0 = x \tag{3.22} \label{3.22}$$

分配律：

$$c (x \mod y) = cx \mod cy \tag{3.23} \label{3.23}$$

有趣的性质：

$$n = \left\lceil \frac n m \right\rceil + \left\lceil \frac {n-1} m \right\rceil + \cdots + \left\lceil \frac {n-m+1} m \right\rceil \tag{3.24} \label{3.24}$$ $$n = \left\lfloor \frac n m \right\rfloor + \left\lfloor \frac {n+1} m \right\rfloor + \cdots + \left\lfloor \frac {n+m-1} m \right\rfloor \tag{3.25} \label{3.25}$$

用$\lfloor mx \rfloor$替换$\eqref{3.25}$中的$n$，可以得到:

$$\lfloor mx \rfloor = \lfloor x \rfloor + \left\lfloor x + \frac 1 m \right\rfloor + \cdots + \left\lfloor x + \frac { m-1} m\right\rfloor \tag{3.26} \label{3.26}$$ $$\sum_{0 \le k \lt n} \lfloor \sqrt k \rfloor = na - {1 \over 3} a^3 - {1\over 2}a^2 - {1\over 6}a, a=\lfloor \sqrt n \rfloor \tag{3.27} \label{3.27}$$

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。