← 返回题目列表

Codeforces · 2028/B

B. 爱丽丝排列历险记

中文机器翻译题面 查看原题

爱丽丝混淆了嬗变和排列这两个词!她有一个通过三个整数 $$$n$$$、$$$b$$$、$$$c$$$ 指定的数组 $$$a$$$:数组 $$$a$$$ 的长度为 $$$n$$$,并通过 $$$a_i = b\cdot (i - 1) + c$$$ for $$$1\le i\le n$$$ 给出。例如,如果 $$$n=3$$$、$$$b=2$$$ 和 $$$c=1$$$,则 $$$a=[2 \cdot 0 + 1, 2 \cdot 1 + 1, 2 \cdot 2 + 1] = [1, 3, 5]$$$。

现在,Alice 非常喜欢 $$$[0, \ldots, n-1]$$$$$$^{\text{*}}$$$ 的排列,并且希望将 $$$a$$$ 转换为排列。在一次操作中,Alice 将 $$$a$$$ 的最大元素替换为 $$$a$$$ 的 $$$\operatorname{MEX}$$$$$$^{\text{†}}$$$。如果 $$$a$$$ 中有多个最大元素,Alice 会选择最左边的一个进行替换。

你能帮助 Alice 算出她需要进行多少次操作才能使 $$$a$$$ 第一次成为排列吗?如果不可能,您应该报告。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

每个测试用例的唯一行包含三个整数 $$$n$$$、$$$b$$$、$$$c$$$ ($$$1\le n\le 10^{18}$$$; $$$0\le b$$$、$$$c\le 10^{18}$$$) — 数组的参数。

输出

对于每个测试用例,如果数组永远不能成为排列,则输出 $$$-1$$$。否则,输出使数组成为排列的最少操作次数。

示例

输入 #1

7
10 1 0
1 2 3
100 2 1
3 0 1
3 0 0
1000000000000000000 0 0
1000000000000000000 1000000000000000000 1000000000000000000

输出 #1

0
1
50
2
-1
-1
1000000000000000000

注意

在第一个测试用例中,数组已经是 $$$[0, 1, \ldots, 9]$$$,因此不需要任何操作。

在第三个测试用例中,起始数组是 $$$[1, 3, 5, \ldots, 199]$$$。第一次操作后,$$$199$$$ 被转换为 $$$0$$$。在第二个操作中,$$$197$$$ 被转换为 $$$2$$$。如果继续这样,将需要 $$$50$$$ 操作来获取数组 $$$[0, 1, 2, 3, \ldots, 99]$$$。

在第四个测试用例中,需要两个操作:$$$[1,1,1] \to [0,1,1] \to [0,2,1]$$$。

在第五个测试用例中,过程是 $$$[0,0,0] \to [1,0,0] \to [2,0,0] \to [1,0,0] \to [2,0,0]$$$。这个过程永远重复,所以数组永远不是排列,答案是$$$-1$$$。