Finding minimum residue of a linear function in O(log M) time

Правка en5, от mango_lassi, 2021-05-15 13:18:17

I saw a blog (thanks to Bugman for finding it!) earlier today asking how to solve the following problem:

Given a linear function $$$ax + b$$$, find the minimum $$$x \geq 0$$$ such that $$$ax + b \in [L, R]\ (\text{mod } M)$$$.

To solve that problem, we can make the following reduction: If $$$gcd(a, M) > 1$$$, we divide everything by the GCD. The $$$x$$$ for which $$$ax + b = L\ (\text{mod } M)$$$ is $$$(L - b) a^{-1}\ (\text{mod } M)$$$. Denote this value by $$$b_0$$$. Then, the minimum $$$x$$$ to get to $$$L + y$$$ is $$$a^{-1} y + b_0\ (\text{mod } M)$$$. This gives us a reduced problem:

Find the minimum value of $$$ay + b \text{ mod } M$$$ over $$$y \leq k$$$.

This seemed pretty hard, but surprisingly I figured out how to do it in $$$\mathcal{O}(\log M)$$$ time! The algorithm is as follows:

In every step, we reduce the modulo from $$$M$$$ to $$$\min(a, M - a) \leq M / 2$$$. This guarantees we do at most $$$\mathcal{O}(\log M)$$$ steps.

To reduce it to $$$a$$$, we consider the first value $$$s$$$ among $$$[0, a)$$$ achieved by $$$ay + b$$$. If $$$b < a$$$, it is $$$b$$$. Otherwise, it is $$$b - M\text{ mod } a$$$. We check in $$$\mathcal{O}(1)$$$ if we reach $$$s$$$ for some $$$y \leq k$$$. If we do, set $$$M$$$ to $$$a$$$, $$$a$$$ to $$$-M \text{ mod } a$$$ and $$$b$$$ to $$$s$$$. Otherwise, output $$$b$$$ as the first $$$a$$$ values are the only values such that the previous value was larger, thus if we never attain them, the first value we attain is the largest we do.

To reduce it to $$$M - a$$$, we consider the first value $$$s = b \text{ mod } M - a$$$ among $$$[0, M - a)$$$ achieved by $$$ay + b$$$. If we reach $$$s$$$ for some $$$y \leq k$$$, set $$$M$$$ to $$$M - a$$$, $$$a$$$ to $$$a \text{ mod } M - a$$$ and $$$b$$$ to $$$s$$$. Otherwise, we can calculate the number of steps to go from $$$v$$$ to $$$v - (M - a)$$$ for $$$v \geq M - a$$$, and from this the smallest value we can reach with $$$y \leq k$$$.


What I wanted to ask is, is this a known problem, and is there a simpler or perhaps even faster solution to it? The problem seems fairly simple, so I doubt nobody has thought about it before.

Теги #number theory, #euclidean algorithm, #continued fractions


  Rev. Язык Кто Когда Δ Комментарий
en5 Английский mango_lassi 2021-05-15 13:18:17 829 Remove binary search
en4 Английский mango_lassi 2021-05-15 12:45:36 1404 Reverted to en2
en3 Английский mango_lassi 2021-05-15 02:10:10 1408 Turns out the other case handled in my original solution was pointless >_>. I removed it, much simplifying the explanation and code :)
en2 Английский mango_lassi 2021-05-14 06:13:03 88 blog found
en1 Английский mango_lassi 2021-05-14 04:28:14 4162 Initial revision (published)