操作によって得られる数列\(A\) は \(A_i=|A_{i+1}-A_{i+2}|\) を満たします。 よって、\(A_N,A_{N-1}\) が決まれば、後ろから順番に全ての要素が一意に定まります。

\(A_{N-1}\) を全探索し、それぞれについて \(A_1, A_2\) を求めます。

ユークリッドの互除法と同じ要領で \(O(\log \min (A_N,A_{N-1}))\) で \(A_1\) の値を求めることができます。(証明は以下)

よってこの問題を \(O(M \log M)\) で解くことができます。

証明

\(A_N \ge A_{N-1}\) を仮定します。\(A_N < A_{N-1}\) の場合は \(A_{N-2}\) を求めてから \(A_{N-1}, A_{N-2}\) に同じことを適用して考えます。

\(A_N = x, A_{N-1} = y\) とします。

\(x=y\) または \(y=0\) のとき、\(A = (\ldots,0,x,x,0,x,x)\) のように続くため、\(A_1\) を容易に求められます。

以下では \(x>y>0\) を仮定します。

\(x = yq + r\) \((q = \lfloor x/y\rfloor, 0 \leq r < y)\) とします。

\(q\) が偶数のとき、\(q=2t\) とすると、 \((A_{N-3t}, A_{N-3t-1}) = (r, y)\) となります。
\(x>2y\) ならば、\(3\) 回で \((x,y) \rightarrow (y,x-y) \rightarrow(x-y,x-2y) \rightarrow(x-2y, y)\) となるからです。

\(q\) が奇数のとき、\(q=2t+1\) とすると、 \((A_{N-3t-1}, A_{N-3t-2}) = ( y,r)\) となります。

\(O(1)\) のステップで \((x,y) \rightarrow (y,r)\) または \((r,y)\) に置き換えることができるため、ユークリッドの互除法と同じ要領で \(O(\log y)\) で \(A_1\) を計算できます。