CF2028B Alice's Adventures in Permuting

Alice 把 transmutation（转化）和 permutation（排列）这两个词搞混了！她有一个由三个整数 $n$、$b$、$c$ 指定的数组 $a$：数组 $a$ 的长度为 $n$，其中 $a_i = b \cdot (i - 1) + c$，$1 \leq i \leq 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$ 变成一个排列吗？如果永远无法变成排列，请输出 $-1$。 $^{\text{∗}}$ 长度为 $n$ 的排列是由 $n$ 个互不相同的整数 $0$ 到 $n-1$ 组成的数组，顺序任意。请注意，这与通常的排列定义略有不同。例如，$[1,2,0,4,3]$ 是一个排列，但 $[0,1,1]$ 不是排列（$1$ 在数组中出现了两次），$[0,2,3]$ 也不是排列（$n=3$ 但数组中有 $3$）。 $^{\text{†}}$ 一个数组的 $\operatorname{MEX}$ 是不在该数组中的最小非负整数。例如，$[0, 3, 1, 3]$ 的 $\operatorname{MEX}$ 是 $2$，$[5]$ 的 $\operatorname{MEX}$ 是 $0$。

每个测试点包含多组测试数据。第一行包含测试用例数 $t$（$1 \leq t \leq 10^5$）。 接下来每组测试数据一行，包含三个整数 $n$、$b$、$c$（$1 \leq n \leq 10^{18}$，$0 \leq b, c \leq 10^{18}$），表示数组的参数。

对于每组测试数据，如果数组永远无法变成排列，输出 $-1$。否则，输出最少需要多少次操作才能第一次将数组变成排列。

在第一个测试用例中，数组已经是 $[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$。 由 ChatGPT 4.1 翻译