If \(A+B-1 \leq M\), the answer is \(M+1\). Let us consider the other case.

For \(x\) such that \(0 \leq x \leq V\), we can transition from \(x\) to \(x-A,x-B,x+A,x+B\), but since \(M \leq A+B-2\), just two of them are within \([0,M]\). Thus, we can see that the transition of \(x\) looks like one of the following two:

• \(+A\) if possible, \(-B\) if possible, \(+A\) if possible, \(-B\) if possible, \(\cdots\)

• \(+B\) if possible, \(-A\) if possible, \(+B\) if possible, \(-A\) if possible, \(\cdots\)

Additionally, neither of them goes into a loop. If we assume otherwise, since \(gcd(A, B)=1\), the length of the loop would be at least \(A+B\), which implies that \(V\) has taken \(A+B\) or more different values, which contradicts with \(M+1 < A+B\).

From the fact that they do not go into a loop, we can also see that each of the two strategies above does not revisit the same value.

Let us count the number of values \(x\) can take in the strategy with \(+A,-B\). We can redefine this strategy as follows:

• let \(x:=x+A\) and then replace \(x\) with the remainder when \(x\) is divided by \(B\).

We will become unable to do the operation at the moment \((x\bmod B)>M-A\) holds. Thus, what we want to solve is the following problem:

• find the smallest integer \(k\) such that \((V+kA \bmod B) \geq M-A+1\).

If \((V\bmod B) \geq M-A+1\), the answer is obviously \(k=0\), so let us consider the other case.

Let us rephrase the problem and find the smallest \(k\) such that \(M-A+1-(V \bmod B) \leq (kA \bmod B) \leq B-1-(V \bmod B)\).

More generally, we want to solve the following problem.

• Given are integers \(H,W,L,R\). A ray of light is emitted from the bottom left corner of an \(H \times W\) rectangle diagonally at a \(45\)-degree angle to upper right. Treat this rectangle as a torus. In other words, when the ray hits an edge of the rectangle, it reappears from the opposite edge. Where does the ray hit the interval \([L, R]\) of the bottom edge, measured from the bottom left corner?

It is obvious that this problem is equivalent to the original one with an inequality with modulo. We can solve this problem in a way similar to Euclidean division. It would be tedious to describe it with words, so refer to the following figure (and writer’s submissions).

This algorithm works in \(O(\log(\max(A, B)))\) time, which is fast enough. There are also \(O(\log^2(\max(A, B)))\) solutions for this problem, and we have set a relatively loose time limit to allow them to pass.