Marking

题目描述

有 $N$ 个方格，按索引 $0$ 到 $(N-1)$ 排成一行。 Snuke 将按如下过程标记每个方格。

标记方格 $0$。

重复以下步骤 i - iii 共 $(N-1)$ 次。

用上次标记的方格的索引 $A$ 初始化变量 $x$ 为 $(A+D) \bmod N$。 当方格 $x$ 已被标记时，重复用 $(x+1) \bmod N$ 替换 $x$。 标记方格 $x$。

求 Snuke 在第 $K$ 次标记时标记的方格的索引。 给定 $T$ 个测试用例，求每个测试用例的答案。

输入格式

输入按下述格式自标准输入给出，其中 $\mathrm{test}_i$ 表示第 $i$ 个测试用例： $T$ $\mathrm{test}_1$ $\mathrm{test}_2$ $\vdots$ $\mathrm{test}_T$

每个测试用例按下述格式给出： $N$ $D$ $K$

输出格式

输出 $T$ 行。 第 $i$ 行 $(1\leq i \leq T)$ 应包含第 $i$ 个测试用例的答案。

9
4 2 1
4 2 2
4 2 3
4 2 4
5 8 1
5 8 2
5 8 3
5 8 4
5 8 5

0
2
1
3
0
3
1
4
2

提示

$1\leq T \leq 10^5$ $1\leq K\leq N \leq 10^9$ $1\leq D \leq 10^9$ 输入中的所有数值均为整数。若 $N=4$ 且 $D=2$，Snuke 的标记过程如下。

标记方格 $0$。 （第 $1$ 次迭代）令 $x=(0+2)\bmod 4=2$。 由于方格 $2$ 未被标记，标记它。
（第 $2$ 次迭代）令 $x=(2+2)\bmod 4=0$。 由于方格 $0$ 已被标记，令 $x=(0+1)\bmod 4=1$。 由于方格 $1$ 未被标记，标记它。
（第 $3$ 次迭代）令 $x=(1+2)\bmod 4=3$。 由于方格 $3$ 未被标记，标记它。

标签: AtCoder|abc290D

来源

AtCoder|abc290D