\(A+B-1 \leq M\) のとき，答えは \(M+1\) です． それ以外の場合を考えます．

\(0 \leq x \leq V\) を満たす \(x\) について，\(x\) から遷移可能な数は \(x-A,x-B,x+A,x+B\) ですが，\(M \leq A+B-2\) より，実際に \([0,M]\) 内に収まるのはこのうち \(2\) つだけです． よって，\(x\) を変化させていく様子は，以下の \(2\) 通りのいずれかであるとわかります．

• 可能であれば \(+A\)，可能ならば \(-B\)，可能ならば \(+A\)，可能ならば \(-B\cdots\)

• 可能であれば \(+B\)，可能ならば \(-A\)，可能ならば \(+B\)，可能ならば \(-A\cdots\)

また，これらどちらの方法も，ループすることはありません． 仮にループしたとすると，\(gcd(A,B)=1\) から，ループの長さは少なくとも \(A+B\) であることになります． これはつまり，\(A+B\) 個以上の異なる値を \(V\) が取ったということですが，\(M+1 < A+B\) より矛盾します．

ループしないということから，上の \(2\) つの戦術で同じ値を訪れるということがないこともわかります．

\(+A,-B\) の戦術で \(x\) が取りうる値の個数を数えます． この戦術は，次のようにとらえなおすことができます．

• \(x:=x+A\) としたあと，\(x\) を \(B\) で割った余りへと変化させる．

これ以上操作が行えなくなる瞬間とは，\((x\bmod B)>M-A\) となった瞬間です． よって，次の問題が解ければいいことになります．

• \((V+kA \bmod B) \geq M-A+1\) を満たす最小の整数 \(k\) を求めよ．

\((V\bmod B) \geq M-A+1\) である場合は明らかに \(k=0\) が答えなので，それ以外の場合を考えます．

変形して，\(M-A+1-(V \bmod B) \leq (kA \bmod B) \leq B-1-(V \bmod B)\) を満たす最小の \(k\) を求めることにします．

一般に，次の問題を解くことを考えます．

• 整数 \(H,W,L,R\) が与えられる． \(H \times W\) の長方形の左下から，右斜め上 45 度の角度で光線を発射する． 長方形はトーラスであると考え，長方形の端に当たった光線は反対側から出てくるものとする． 長方形の底辺のうち，左下から距離 \([L,R]\) の区間に初めて光線が当たるのはどこか？

この問題が元の mod の不等式の問題と同値であることは明らかです． そしてこの問題は，ユークリッドの互除法の要領で解くことが可能です． 言葉で説明すると冗長になるので，以下の図（および writer の提出）を参照してください．

このアルゴリズムは \(O(\log(\max(A,B)))\) 時間で動作し，十分高速です． なお，この問題には \(O(\log^2(\max(A,B)))\) 解法も存在するため，これを許容するために TL を大きめに設定してあります．