lhh定理

· · 算法·理论

起因是做一道题时，lhh 把 cnt/i%2 写成了 cnt%2/i（这里 i 从 2 开始每次加 2）。

然后他发现这好像是对的！

于是 lhh 开始尝试拓展这个规律。

于是他发现了：

设 m,d\in\mathbb Z\setminus{0}、i\in\mathbb Z，满足

\gcd(|m|,|d|)=1,\quad d\mid i,\quad d\mid(i\bmod m)

那么。

\frac{i\bmod m}{d}=\left(\frac{i}{d}\right)\bmod m

以及该定理的证明：

令 r=i\bmod m，写成 i=qm+r。由 d\mid i 和 d\mid r，可知 d\mid qm；再由 \gcd(|m|,|d|)=1，得到 d\mid q。于是：

\frac{i}{d}=\frac{q}{d}m+\frac{r}{d}

取模后就是 r/d。

lhh 发现此前没有任何人发现这个规律，于是命名为 lhh 定理。

而且该定理貌似可以在数数题中发挥一定作用，目前有待考证，但这绝对是一个伟大的定理，见证历史。