Gears

2 secs 1024 MB

この問題はクエリごとに $O(1)$ で求めることができます。

歯車の歯数がいくつ分回転しているかはすべての歯車で等しいため、途中の歯車は無視して良いことが分かります。
よって答えは $\lceil \frac{A_Y}{A_X} \rceil$ で求まります。( $\lceil x \rceil$ は $x$ 以上の最小の整数を表します。)

また、 $i+1$ 番目の歯車を ちょうど $1$ 回転させるのに、 $i$ 番目の歯車は $\frac{A_{i+1}}{A_{i}}$ 回転させる必要があることを考えると、
$Y$ 番目の歯車をちょうど $1$ 回転させるのに、 $X$ 番目の歯車は

$\frac{A_{Y}}{A_{Y-1}}$ $×$ $\frac{A_{Y-1}}{A_{Y-2}}$ $×$ $\frac{A_{Y-2}}{A_{Y-3}}$ $...$ $×$ $\frac{A_{X+1}}{A_{X}}$ $=$ $\frac{A_Y}{A_X}$

回転する必要があるとも考えられます。