### Stepavly's blog

By Stepavly, 5 weeks ago, translation,

Can somebody explain how to solve such problem: given values $x$, $L$, $R$, $M$ ($0 \le L \le R \le M - 1$), find minimal $k \ge 0$ such that $L \le (x \cdot k) \mod M \le R$.

This problem appeared in NEERC19 (Golf time) as a subtask, but the editorial not so clearly explains the algorithm for that subtask.

• +33

 » 5 weeks ago, # | ← Rev. 2 →   +8 It's better to give constraints to M, and whether multi-query Solution 1: Brute force algorithm involve only +, - and compare is enough to pass Solution 2: We may first get $x^{-1}$ if $\gcd(x, M) = 1$. Then the answer is $\displaystyle \min_{i = L}^R x^{-1} i$, only involve +, -, compare, and once multiplication. If $d = \gcd(x, M)$, we may divide all variables by d.
•  » » 5 weeks ago, # ^ |   0 You may assume that $M$ is large enough, but fits in 64-bit type. I am interested in solution in $\mathcal{O}(\log M)$.
•  » » » 4 weeks ago, # ^ |   +1
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Um_nik comment is exactly for the same problem as mentioned in this blog. But can you provide some idea/theoretical part? I mean what he is trying to do in the code?Edit:- see this blog