AT_abc156_f [ABC156F] Modularness

有一个长度为 $k$ 的数列 $d_0, d_1, \ldots, d_{k-1}$。 请依次处理以下 $q$ 个查询。 - 第 $i$ 个查询包含三个整数 $n_i, x_i, m_i$。定义长度为 $n_i$ 的数列 $a_0, a_1, \ldots, a_{n_i-1}$，其递推关系如下： $$ \begin{aligned} a_j = \begin{cases} x_i & (j = 0) \\ a_{j-1} + d_{(j-1)\bmod k} & (0 < j \leq n_i - 1) \end{cases} \end{aligned} $$ 请输出满足 $(a_j \bmod m_i) < (a_{j+1} \bmod m_i)$ 的 $j$ 的个数，其中 $0 \leq j < n_i - 1$。 这里，对于两个整数 $y, z\ (z > 0)$，$(y \bmod z)$ 表示 $y$ 除以 $z$ 的余数。

输入按以下格式从标准输入读入。 > $k$ $q$ $d_0$ $d_1$ $\ldots$ $d_{k-1}$ $n_1$ $x_1$ $m_1$ $n_2$ $x_2$ $m_2$ $\ldots$ $n_q$ $x_q$ $m_q$

输出 $q$ 行。 第 $i$ 行输出第 $i$ 个查询的答案。

### 限制条件 - 所有输入均为整数。 - $1 \leq k, q \leq 5000$ - $0 \leq d_i \leq 10^9$ - $2 \leq n_i \leq 10^9$ - $0 \leq x_i \leq 10^9$ - $2 \leq m_i \leq 10^9$ ### 样例解释 1 对于第 $1$ 个查询，按照题意构造的数列 $\{a_j\}$ 为 $3, 6, 7, 11, 14$。 - $(a_0 \bmod 2) > (a_1 \bmod 2)$ - $(a_1 \bmod 2) < (a_2 \bmod 2)$ - $(a_2 \bmod 2) = (a_3 \bmod 2)$ - $(a_3 \bmod 2) > (a_4 \bmod 2)$ 因此，该查询的答案为 $1$。 由 ChatGPT 4.1 翻译