proof - Codeforces

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

proof of this

Theorem: Let $$$p=\lceil\frac km\times2^{64}\rceil$$$, when $$$a_i\le \frac{2^{64}}m$$$, the computation of the lower rounding is exact.

Proof: Let $$$\frac p{2^{64}}=\frac km+\epsilon$$$, where $$$\epsilon\in[0,\frac1{2^{64}})$$$.

$$$ \begin{aligned} \lfloor\{a_i\times \frac p{2^{64}}\}\times m\rfloor&=\lfloor\{a_i\times (\frac km+\epsilon)\}\times m\rfloor\\ &=\lfloor\{a_i\times \frac km+a_i\epsilon\}\times m\rfloor \end{aligned} $$$

Here if $$$\lfloor a_i\times\frac km+a_i\epsilon\rfloor>\lfloor a_i\times \frac km\rfloor$$$ must be wrong, $$$a_i\times \frac km$$$ is at least $$$\frac1m$$$ away from $$$\lfloor a_i\times \frac km\rfloor+1$$$, so as long as $$$a_i\epsilon<\frac1m$$$ it's OK, let's continue the derivation.

$$$ \begin{aligned} &=\lfloor\{a_i\times \frac km+a_i\epsilon\}\times m\rfloor\\ &=\big\lfloor\left(\{a_i\times \frac km\}+a_i\epsilon\right)m\big\rfloor\\ &=\lfloor\{a_i\times \frac km\}\times m+a_im\epsilon\rfloor \end{aligned} $$$

Since $$$\{a_i\times\frac km\}\times m$$$ is an integer, the result is exact as long as $$$a_im\epsilon<1$$$.

The $$$a_i\epsilon<\frac1m$$$ and $$$a_im\epsilon<1$$$ are the same, and then the condition can be rewritten as $$$a_i\le\frac{2^{64}}m$$$ according to $$$\epsilon<\frac1{2^{64}}$$$.

platelet's blog