Stepavly's blog

Need help in diophantine equations
By Stepavly, 4 years ago, translation, In English

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.

  • Vote: I like it
  • +33
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You may assume that $$$M$$$ is large enough, but fits in 64-bit type. I am interested in solution in $$$\mathcal{O}(\log M)$$$.

    → Reply