Carnival Wheel

We need maximize

$(a + kb) \bmod l$

over all integers $k \ge 0$.

At first glance this sounds like “spin forever and choose the best landing spot,” but modulo arithmetic does not let the sequence be infinite in any interesting way. There are only $l$ sections, so eventually the positions repeat.

Reachability

Each spin adds $b$ modulo $l$. The key invariant is based on

$g = \gcd(l,b).$

Because $g$ divides both $l$ and $b$, adding $b$ never changes the current position modulo $g$:

$a + kb \equiv a \pmod g.$

Taking modulo $l$ also does not change this fact, because $l$ is divisible by $g$. So every reachable section must have the same remainder as $a$ modulo $g$.

Now the other direction: are all such sections reachable? Yes. The step size $b$ moves around the circle in jumps of size $g$ effectively, and after dividing everything by $g$, the step becomes coprime with the new circle length. That means it cycles through every residue in that reduced circle. So the reachable sections are exactly:

$x \in [0,l-1] \quad \text{where} \quad x \equiv a \pmod g.$

No hidden trap. That is the whole problem.

Finding the maximum

We want the largest number less than $l$ with the same remainder as $a$ modulo $g$.

The cleanest way is to start at $l-1$, the biggest possible prize, and move downward until the remainder matches:

ans = l - 1
while ans % g != a % g:
    ans--

This loop runs at most $g$ times, and $g \le l \le 5000$, so it is easily fast enough.

There is also a one-line formula:

$\text{ans} = (l-1) - ((l-1-a) \bmod g).$

Why does that work? Starting from $l-1$, we subtract just enough to land on a number congruent to $a$ modulo $g$.

Examples

For $l=8, a=2, b=4$:

$g=\gcd(8,4)=4.$

Reachable positions must be congruent to $2 \pmod 4$, so they are $2$ and $6$. Maximum is $6$.

For $l=2, a=0, b=6$:

$g=\gcd(2,6)=2.$

Reachable positions must be congruent to $0 \pmod 2$, so only section $0$ works. Maximum is $0$.

That is it. The wheel is not magic; it is just gcd wearing a carnival hat.