公式解説とほとんど同じですが、優先度付きキューを使いません。

前処理

まず、\(A_i \le A_{i+1}\) のとき、任意の整数 \(x\) について \((x \bmod A_i) \bmod A_{i+1} = x \bmod A_i\) が成り立ちます。

よって、ここの \(A_{i+1}\) は計算結果に影響を与えないため、削除しても構いません。

この操作を繰り返すことで \(A_1 > A_2 > \cdots > A_N\) となるため、これを仮定します。

再帰関数の定義

整数 \(x \in [0, X)\) であって、 \((\cdots((x \bmod A_{t}) \bmod A_{t+1}) \cdots )\bmod A_N = 0\) を満たすものの個数を、 \(f(X,t)\) と定義します。

\(f(X,t)\) は公式解説のように以下のように漸化式で展開できます。

\[ f(X,t) = \begin{cases} f(A_t, t+1) \times \left\lfloor \frac{X}{A_t} \right\rfloor + f(X \bmod A_t, t+1) & (t \le N) \\ 0 & (t = N+1 ~ \text{and} ~ X=0)\\ 1 & (t = N+1 ~ \text{and} ~ X>0) \end{cases} \]

計算量削減

上の式において、 \(X < A_t\) なら \(f(X,t) = f(X,t+1)\) となります。したがって、\(X \ge A_t\) となる最小の \(t\) まではすべてスキップすることができます。この \(t\) は、 \(A\) が単調減少であることを利用して二分探索を用いると \(O(\log N)\) 時間で特定できます。

そして、そのとき、 \(X \bmod A_t\) は必ず半分以下になります。これは公式解説と同様です。

よって、もし \(f(A_i, i+1)\) がすべて前計算できているとしたら、 一本道の再帰になり、\(O(\log X)\) 回で終わります。

よって、\(f(X,i)\) は前計算を行った後 \(O(\log N \log X)\) 時間で求められます。

前計算は後ろから

\(f(A_i, i+1)\) は \(i=N,N-1,\cdots, 1\) の順で計算すると、すべての必要な \(f(A_t, t+1)\) の値がすでに前計算された状態となるため、一本道の再帰で正しい値が求まります。

あるいは、後ろから for 文を回すのではなく、最初から（答えに必要な） \(f(X+1, 1)\) を計算するときにメモ化再帰でそれらの値を求めてもよいです。

答え

\(f(X+1, 1) - 1\) が答えになります。

時間計算量は \(O(N \log N \log X)\)、空間計算量は \(O(N)\)です。