上下取整函数的关系以及一些重要性质(附证明)

今天(2022.12.7)的lc每日一题, 虽然是中等但也有很多需要注意的点, 看到了0x3f大佬的题解才发现自己知识点的太多不足, 比如下面这个式子:(出自具体数学练习3.12) ⌈ n m ⌉ = ⌊ n + m − 1 m ⌋ = ⌊ n − 1 m ⌋ + 1. \left\lceil \frac{n}{m} \right\rceil = \left\lfloor \frac{n+m-1}{m} \right\rfloor = \left\lfloor \frac{n - 1}{m} \right\rfloor + 1. ⌈mn​⌉=⌊mn+m−1​⌋=⌊mn−1​⌋+1. 本文主要给出取整函数的一些内容, 包括几个重要的取整函数以及上下取整函数之间的关系等.

参考了具体数学1, Wikipedia2以及3.

这里的一些定义, 记号等均参考了具体数学. 如无特殊说明, 均价定 x x x 为正整数.

设 x ∈ R x\in\mathbb R x∈R, 则

⌊ x ⌋ \lfloor x\rfloor ⌊x⌋表示 x x x的整数部分(integer part)

{ x } \{x\} {x}表示 x x x的分数部分(fractional part), (不与单元素集合混淆的情况下)

关系: x = ⌊ x ⌋ + { x }    ⟺    { x } = x − ⌊ x ⌋ . x=\lfloor x\rfloor+\{x\}\iff\{x\}=x-\lfloor x\rfloor. x=⌊x⌋+{x}⟺{x}=x−⌊x⌋.

(下取整表示)设 m , n ∈ N ∗ m,n\in\mathbb N^* m,n∈N∗, 则 n = m ⋅ ⌊ n / m ⌋ ⏟ 商 + n   m o d   m ⏟ 余数 (1) n=m\cdot\underbrace{\lfloor n/m \rfloor}_{\text{商}}+\underbrace{n\bmod m}_{\text{余数}}\tag{1} n=m⋅商 ⌊n/m⌋​​+余数 nmodm​​(1) 其中, n   m o d   m ∈ [ 0 , m ) n\bmod m\in[0, m) nmodm∈[0,m).

由 ( 1 ) (1) (1), 得 n   m o d   m = n − m ⌊ n / m ⌋ n\bmod m=n-m\lfloor n/m \rfloor nmodm=n−m⌊n/m⌋ 推广:(设 x , y ∈ R x,y\in\mathbb R x,y∈R) x   m o d   y = x − y ⌊ x / y ⌋ ,   y ≠ 0. x\bmod y=x-y\lfloor x/y \rfloor,\ y\ne0. xmody=x−y⌊x/y⌋, y=0. 于是: { x   m o d   y ∈ [ 0 , y ) , y > 0 x   m o d   y ∈ ( y , 0 ] , y < 0 \begin{cases} x\bmod y\in [0,y),&y>0\\ x\bmod y\in (y,0],&y{x}}​=⌊x⌋,=⌈x⌉,={x}.​

并有:(只关注内层作用) ⌊ ⌈ x ⌉ ⌋ = ⌈ x ⌉ , ⌈ ⌊ x ⌋ ⌉ = ⌊ x ⌋ , \begin{aligned} \Big\lfloor \lceil x \rceil \Big\rfloor &= \lceil x \rceil, \\ \Big\lceil \lfloor x \rfloor \Big\rceil &= \lfloor x \rfloor, \end{aligned} ⌊⌈x⌉⌋⌈⌊x⌋⌉​=⌈x⌉,=⌊x⌋,​

⌊ x ⌋ + ⌈ − x ⌉ = 0 , − ⌊ x ⌋ = ⌈ − x ⌉ , − ⌈ x ⌉ = ⌊ − x ⌋ . \begin{aligned} \lfloor x \rfloor +\lceil -x \rceil &= 0, \\ -\lfloor x \rfloor &= \lceil -x \rceil, \\ -\lceil x \rceil &= \lfloor -x \rfloor. \end{aligned} ⌊x⌋+⌈−x⌉−⌊x⌋−⌈x⌉​=0,=⌈−x⌉,=⌊−x⌋.​

并且: ⌊ x ⌋ + ⌊ − x ⌋ = { 0 ,  若   x ∈ Z , − 1 ,  若   x ∉ Z , ⌈ x ⌉ + ⌈ − x ⌉ = { 0 ,  若   x ∈ Z , 1 ,  若   x ∉ Z . \lfloor x \rfloor + \lfloor -x \rfloor = \begin{cases} 0,&\text{ 若 }\ x\in \mathbb{Z},\\ -1,&\text{ 若 }\ x\not\in \mathbb{Z}, \end{cases} \\[5pt] \lceil x \rceil + \lceil -x \rceil = \begin{cases} 0,&\text{ 若 }\ x\in \mathbb{Z},\\ 1,&\text{ 若 }\ x\not\in \mathbb{Z}. \end{cases} ⌊x⌋+⌊−x⌋={0,−1,​ 若  x∈Z, 若  x∈Z,​⌈x⌉+⌈−x⌉={0,1,​ 若  x∈Z, 若  x∈Z.​ 针对小数部分( { x } = x − ⌊ x ⌋ \{x \} = x - \lfloor x \rfloor {x}=x−⌊x⌋): { x } + { − x } = { 0 ,  若   x ∈ Z , 1 ,  若   x ∉ Z . \{ x \} + \{ -x \} = \begin{cases} 0,&\text{ 若 }\ x\in \mathbb{Z},\\ 1,&\text{ 若 }\ x\not\in \mathbb{Z}. \end{cases} {x}+{−x}={0,1,​ 若  x∈Z, 若  x∈Z.​

⌈ x ⌉ ⩾ x \lceil x\rceil\geqslant x ⌈x⌉⩾x; ⌊ x ⌋ ⩽ x \lfloor x\rfloor\leqslant x ⌊x⌋⩽x; ⌊ x ⌋ ⩽ ⌈ x ⌉ \lfloor x \rfloor \leqslant \lceil x \rceil ⌊x⌋⩽⌈x⌉.

⌊ x ⌋ = x    ⟺    x ∈ Z    ⟺    ⌈ x ⌉ = x \lfloor x\rfloor=x\iff x\in \mathbb Z\iff \lceil x\rceil=x ⌊x⌋=x⟺x∈Z⟺⌈x⌉=x;

If x ∉ Z x\notin \mathbb Z x∈/Z, then ⌈ x ⌉ − ⌊ x ⌋ = [ x  not an integer ] = 1 \lceil x\rceil-\lfloor x\rfloor=[x\ \text{not an integer}]=1 ⌈x⌉−⌊x⌋=[x not an integer]=1. 另一种表述: ⌈ x ⌉ − ⌊ x ⌋ = [ x 是否为整数 ] = { 0 ,  若   x ∈ Z , 1 ,  若   x ∉ Z . \lceil x \rceil - \lfloor x \rfloor = [x\text{是否为整数}]= \begin{cases} 0,&\text{ 若 }\ x\in \mathbb{Z},\\ 1,&\text{ 若 }\ x\not\in \mathbb{Z}. \end{cases} ⌈x⌉−⌊x⌋=[x是否为整数]={0,1,​ 若  x∈Z, 若  x∈Z.​

x − 1 < ⌊ x ⌋ x-1\lceil x\rceil x+1>⌈x⌉, so we have: x − 1 < ⌊ x ⌋ ⩽ x ⩽ ⌈ x ⌉ < x + 1. x-1r个组:q+1件物品m−r个组:q件物品​

那么在第 k k k组( 1 ⩽ k ⩽ m 1\leqslant k\leqslant m 1⩽k⩽m)中有多少物品?

应该是: ⌈ n − k + 1 m ⌉ \left\lceil \frac {n-k+1}m\right\rceil ⌈mn−k+1​⌉

证明:

将 n = q m + r n=qm+r n=qm+r代入上式, 得到: ⌈ n − k + 1 m ⌉ = ⌈ q m + r − k + 1 m ⌉ = ( ∗ ) q + ⌈ r − k + 1 m ⌉ \left\lceil \frac {n-k+1}m\right\rceil=\left\lceil \frac {qm+r-k+1}m\right\rceil\stackrel{(*)}{=}q+\left\lceil \frac {r-k+1}m\right\rceil ⌈mn−k+1​⌉=⌈mqm+r−k+1​⌉=(∗)q+⌈mr−k+1​⌉ 应用边界条件: 1 ⩽ k ⩽ m ,   0 ⩽ r < m 1\leqslant k\leqslant m,\ 0\leqslant r