MornStar @ 2023-03-14 21:18:34
\left \lfloor \frac{a}{b} \right \rfloor\mod{c}=\left \lfloor \frac{a\mod{bc}}{b} \right \rfloor
带进去很多值都是对的，但是不知道式子是对还是错。
有没有什么方法判断一下。
by Terrible @ 2023-03-14 21:35:57
限定对 m 取模的结果在 [0,m) 中。
模的性质\quad a\bmod b=a-\left\lfloor\dfrac{a}{b}\right\rfloor b.
引理1\quad 若 a,b,n\in\mathbb{N}_+，则 \left\lfloor\dfrac{n}{ab}\right\rfloor
=\left\lfloor\dfrac{\left\lfloor\frac{n}{a}\right\rfloor}{b}\right\rfloor.
引理2\quad a,b,c\in\mathbb N_+ ，且 b|c，则有 \left\lfloor\dfrac{a}{b}\right\rfloor+\left\lfloor\dfrac{c}{b}\right\rfloor=\left\lfloor\dfrac{a+c}{b}\right\rfloor.
证明：
\left\lfloor\dfrac{a}{b}\right\rfloor\bmod c=\left\lfloor\dfrac{a}{b}\right\rfloor-\left\lfloor\dfrac{\left\lfloor\dfrac{a}{b}\right\rfloor}{c}\right\rfloor c=\left\lfloor\dfrac{a}{b}\right\rfloor-\left\lfloor\dfrac{a}{bc}\right\rfloor c
=\left\lfloor\dfrac{a}{b}\right\rfloor-\left\lfloor\dfrac{\left\lfloor\dfrac{a}{bc}\right\rfloor bc}{b}\right\rfloor=\left\lfloor\dfrac{a-\left\lfloor\dfrac{a}{bc}\right\rfloor bc}{b}\right\rfloor
=\left\lfloor\dfrac{a\bmod bc}{b}\right\rfloor.$ $\square