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.

It's better to give constraints to M, and whether multi-query

Solution 1: Brute force algorithm involve only

`+, -`

and compare is enough to passSolution 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.You may assume that $$$M$$$ is large enough, but fits in 64-bit type. I am interested in solution in $$$\mathcal{O}(\log M)$$$.

See here

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