\(1 \leq n <A+B\) より，操作の過程で常に \(0 \leq x <A+B\) が成立するようにしても答えが変わりません． これは次のように証明できます． まず，\(n=Au+Bv\) のような作り方を目指すとします． \(1 \leq n<A+B\) より，\(u,v\) のちょうど一方が正で他方が非正です． 例えば \(u> 0, v \leq 0\) だとすると，次のように操作すればよいです．

• 以下の操作を \(u\) 回行う．
  • \(x \geq B\) である限り，\(x \to x-B\) と操作する．
  • \(x \to x+A\) と操作する．
• 最後に余った回数だけ \(x \to x-B\) と操作する．

\(u \leq 0,v>0\) の場合も同様に行えます．

\(u>0\) の場合を \(+A\) パターン，\(v>0\) の場合を \(+B\) パターンと呼ぶことにします．

ここで注目すべきは，\(n\) の値によらず行う手順は一定だということです． そして，\(+A\) パターンの操作を繰り返していくと，いつか \(x=0\) に戻ってきます． この操作の様子を逆順にすると \(+B\) パターンになります． 別の言い方をすれば，それぞれのパターンの移動は \(0,1,\cdots,A+B-1\) の \(A+B\) 頂点からなるサイクルであり，パターンの違いはサイクルを回る順序の違いでしかないということです．

最終的に求めたいのは，各頂点への”最短路”です． 結局，各パターンについて，最初のある回数までの移動は最短路に対応する，という回数が求まります．

あとは以下の問題が（高速に）解ければよいです．

• 整数 \(A,B,X,Y,N,C\) が与えられる．整数 \(x=0,cur=0,ans=0\) を持った状態から初めて，以下の操作を\(N\) 回繰り返す．最終的な \(ans\) の値を求めよ．
  • \(x<B\) の時
    • \(x<C\) なら \(ans\operatorname{+=}cur\) とする．
    • \(x\operatorname{+=}A\)，\(cur\operatorname{+=}X\) とする．
  • \(x\geq B\) の時
    • \(x<C\) なら \(ans\operatorname{+=}cur\) とする．
    • \(x\operatorname{-=}B\)，\(cur\operatorname{+=}Y\) とする．

実は，これを一般化した次のような問題が解けます．

• 整数 \(A,B,C,N\) 及び，あるモノイド \(M\) の元 \(AX,AY,BX,BY\) が与えられる．整数 \(x=0\)，\(M\) の元 \(cur=id,ans=id\) を持った状態から初めて，以下の操作を\(N\) 回繰り返す．最終的な \(ans\) の値を求めよ．
  • \(x<B\) の時
    • \(x<C\) なら \(ans\operatorname{:=}AX \cdot ans\) とし，\(x\geq C\) なら \(ans\operatorname{:=}AY \cdot ans\) とする．
    • \(x\operatorname{+=}A\) とする．
  • \(x\geq B\) の時
    • \(x<C\) なら \(ans\operatorname{:=}BX \cdot ans\) とし，\(x\geq C\) なら \(ans\operatorname{:=}BY \cdot ans\) とする．
    • \(x\operatorname{-=}B\) とする．

これは floor_sum(gauss_sum) を求めるのと似た要領で求められます． 例えば，\(A<B\) のときを考えます． \(B=pA+q\) (\(q < A\)) と表したとすると，\(p\) 回の \(+A\) と \(1\) 回の \(-B\) をまとめて \(-q\) の動きにすることができます． \(AX,AY,BX,BY,C\) の値も適宜変更する必要がありますが，ここで細かい場合分けが必要になります． 詳細は省略しますので，回答例を参考にしてください． \(A>B\) のケースも同様に処理できます．

以上の方針で解法を設計すれば，\(1\) ケースあたり\(O(\operatorname{poly} \log (A+B))\) 時間のアルゴリズムになります． なお，回答例は \(1\) ケースあたり \(O(\log^2 \max(A+B))\) で動作しています．

回答例(C++)