#ABC156F. Modularness
Modularness
题目描述
We have a sequence of numbers: .
Process the following queries in order:
- The -th query contains three integers , , and . Let be the following sequence of numbers:$$ \begin{aligned} a_j = \begin{cases} x_i & ( j = 0 ) \\ a_{j - 1} + d_{(j - 1)~\textrm{mod}~k} & ( 0 \lt j \leq n_i - 1 ) \end{cases}\end{aligned} $$Print the number of such that $(a_j~\textrm{mod}~m_i) \lt (a_{j + 1}~\textrm{mod}~m_i)$.
Here denotes the remainder of divided by , for two integers and .
我们有一串 数字: .
请依次处理以下 个查询:
- -查询包含三个整数 、 和 。假设 是以下 个数字的序列:
$$
\begin{aligned} a_j = \begin{cases} x_i & ( j = 0 ) \\ a_{j - 1} + d_{(j - 1)~\textrm{mod}~k} & ( 0 \lt j \leq n_i - 1 ) \end{cases}\end{aligned}
$$
打印 $j~(0 \leq j \lt n_i - 1)$ 中 $(a_j~\textrm{mod}~m_i) \lt (a_{j + 1}~\textrm{mod}~m_i)$ 的个数。
这里的 表示两个整数 和 的余数 除以 的余数。
输入格式
输入内容按以下格式标准输入:
输出格式
打印 行。
-th 行应包含对 -th 查询的响应。
样例 #1
样例输入 #1
3 1
3 1 4
5 3 2
样例输出 #1
1
样例 #2
样例输入 #2
7 3
27 18 28 18 28 46 1000000000
1000000000 1 7
1000000000 2 10
1000000000 3 12
样例输出 #2
224489796
214285714
559523809
说明
数据规模与约定
- 所有输入值均为整数。
样例 解释
对于第一个查询,序列 { } 将是 。
因此,该查询的回复应为 。