Блог пользователя Stepavly

Need help in diophantine equations
Автор Stepavly, 4 года назад, По-русски

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
  • Проголосовать: не нравится

»
4 года назад, # |
← 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.

→ Ответить