AT_abc186_e [ABC186E] Throne

题目描述

在圆周上有 $N$ 把椅子排成一圈。其中有一把是“玉座”。

高桥君一开始坐在距离玉座顺时针数第 $S$ 把椅子上，并重复以下操作：

操作：从当前所坐的椅子出发，顺时针移动 $K$ 把椅子并坐下。

请问高桥君第一次能够坐到玉座是在第几次操作之后？如果永远无法坐到玉座，请输出 $-1$。

请回答 $T$ 组测试用例。

输入格式

输入从标准输入中读入。第 $1$ 行为：

$T$

接下来 $T$ 行，每行表示一个测试用例，格式如下：

$N$ $S$ $K$

输出格式

对于每个测试用例，输出答案。每个测试用例输出一行。

输入输出样例 #1

输入 #1

4
10 4 3
1000 11 2
998244353 897581057 595591169
10000 6 14

输出 #1

2
-1
249561088
3571

说明/提示

限制条件

• $1 \leq T \leq 100$
• $2 \leq N \leq 10^9$
• $1 \leq S < N$
• $1 \leq K \leq 10^9$

样例解释 1

在第 $1$ 个测试用例中，有 $10$ 把椅子，高桥君最初坐在距离玉座顺时针数第 $4$ 把椅子上。顺时针移动 $3$ 把椅子的操作进行 $2$ 次后，他可以坐到玉座上。在第 $2$ 个测试用例中，高桥君永远无法坐到玉座，因此输出 $-1$。

由 ChatGPT 4.1 翻译