matsueushi

AtCoder diverta 2019 Programming Contest D - DivRem Number

2022-6-11 19:45

$t = \lfloor n/m\rfloor = n \mod m$ とおくと $0 \le t < m$であり、$n=\alpha m + t$ とおける。 $t$ の条件から $\alpha = \lfloor n/m\rfloor = t$ だから結局 $n = t(m+1)$ とかける。

$n = t(m+1) \ge t^2$ より、$t \le \sqrt{n}$ を探索すれば良い。