バス停 \(i\) に着く時刻が \(x_i\) のとき、次に乗ることができる最も早いバスは時刻 \(\lceil \frac{x_i}{P_i} \rceil \cdot P_i\) に発車するバスであるため、バス停 \((i+1)\) に着く時刻 \(x_{i+1}\) は

\[x_{i+1} = \left\lceil \frac{x_i}{P_i} \right\rceil \cdot P_i + T_i \tag{1}\]

と求まります。 よって、高橋君がある時刻 \(q\) に自宅を出発するときの、出発してから青木君の家に到着するまでにかかる時間 \(f(q)\) は、 上式 (1) によって \(i\) の小さい方から順に \(x_i\) を計算していくことで、全体で \(\Theta(N)\) 時間で計算できます。

しかし、\(Q\) 個のクエリ \(q_1, q_2, \ldots, q_Q\) それぞれについて \(f(q_j)\) を愚直に計算すると全体で \(\Theta(NQ)\) 時間かかり、実行制限時間に間に合わせることは絶望的です。

実は、後で述べるように \(f\) は \(L \coloneqq \mathrm{lcm}(P_1, P_2, \ldots, P_{N-1}) \leq \mathrm{lcm}(1, 2, \ldots, 8) = 840\) を周期とします。

よって、\(f(0), f(1), \ldots, f(L-1)\) の \(L\) 個の値だけを、あらかじめ全体で \(O(NL)\) 時間で求めておけば、 各クエリ \(q_j\) に対する \(f(q_j)\) の値は、\(q_j\) を \(L\) で割った余り \(q_i \% L\) に対する \(f\) の値 \(f(q_i \% L)\) と等しいため、 これを参照して \(O(1)\) 時間で求めることができ、本問題を全体で \(O(NL + Q)\) 時間で解くことができます。

\(f\) が \(L\) を周期とすることの証明

\(q \equiv q' \pmod{L}\) を仮定して \(f(q) = f(q')\) となることを示します。 そのためには、高橋君が自宅を出発する時刻が \(q, q'\) である場合それぞれの、バス停 \(i\) に到着する時刻を \(x_i, x'_i\) とし、

すべての \(i\) について、\(x_i \equiv x'_i \pmod{L}\) と \(x_i - x_{i-1} = x'_i - x'_{i-1}\) が成り立つ

を示せば十分です。( \(x_i - x_{i-1}\) と \(x'_i - x'_{i-1}\) が、それぞれ \(q, q'\) に対応する、「バス停 \((i-1)\) に着いてからバス停 \(i\) に着くまでにかかる時間」であるため、これが全ての \(i\) で等しいことが言えれば、\(f(q) = f(q')\) が言えます。)

\(i\) に関する帰納法で示します。 まず、仮定 \(q \equiv q' \pmod{L}\) から \(x_1 = q + X \equiv q' + X = x'_1 \pmod{L}\)です。 以下、\(i\) で主張が成り立つと仮定し、\((i+1)\) でも成り立つことを示します。

まず、\(x_{i+1} - x_i\) について、式 (1) から

\[ \begin{aligned} x_{i+1} - x_i &= \left\lceil \frac{x_i}{P_i} \right\rceil \cdot P_i + T_i - x_i\\ &= \left\lfloor \frac{x_i + P_i - 1}{P_i} \right\rfloor \cdot P_i + T_i - x_i\\ &= (x_i + P_i - 1) - ((x_i + P_i - 1) \% P_i )+ T_i - x_i\\ &= P_i + T_i - 1 - ((x_i - 1) \% P_i ) \tag{2} \end{aligned} \]

です。\(x'_{i+1} - x'_i\) についても同様に、

\[ x'_{i+1} - x'_i = P_i + T_i - 1 - ((x'_i - 1) \% P_i ) \tag{3} \]

です。

帰納法の仮定 \(x_i \equiv x'_i \pmod{L}\) と \(L\) が \(P_i\) の倍数であることから、\(x_i \equiv x'_i \pmod{P_i}\) であり、よって \((x_i - 1) \% P_i = (x'_i - 1) \% P_i \) です。したがって、式 (2), (3) の最右辺は等しく、\(x_{i+1} - x_i = x'_{i+1} - x'_i\) が成り立ちます。 また、これと帰納法の仮定 \(x_i \equiv x'_i \pmod{L}\) から直ちに \(x_{i+1} \equiv x'_{i+1}\pmod{L}\) も得られます。