AT_utpc2025_l.Linear Floor

给定整数 $N, K$ 和一个长度为 $N$ 的整数序列 $X = (X_0, X_1, \ldots, X_{N-1})$。

满足以下所有条件的整数三元组 $(M, A, B)$ 被称为良好组合：

• $1 \leq M < 2^{30}$
• 对于 $k = 0, 1, \ldots, N-1$，都有 $X_k = \left\lfloor \frac{A k + B}{M} \right\rfloor$。

可以证明，在题目限定的条件下，良好组合的个数是有限的。记这个数量为 $C$。

请判断 $K \leq C$ 是否成立。如果成立，输出按字典序排列的第 $K$ 小的良好组合；否则输出 -1。

有 $T$ 个测试用例，请分别作答。

输入通过标准输入给出，格式如下：

$T$ $\text{case}_1$ $\text{case}_2$ $\vdots$ $\text{case}_T$

第 $i$ 个测试用例 $\text{case}_i$ 的格式如下：

$N$ $K$ $X_0$ $X_1$ $\ldots$ $X_{N-1}$

请输出 $T$ 行。

对于第 $i$ 个测试用例，如果 $K \leq C$ 成立，则输出按字典序第 $K$ 小的良好组合 $M, A, B$，以半角空格分隔；否则输出 -1。

部分分

• 对于满足附加条件 $K = 1$ 的数据集，得到 2 分。
• 对于满足附加条件 $K \leq 10$ 的数据集，得到额外 18 分。

样例说明 1

对于第 $1$ 个测试用例，所有良好组合按字典序依次是 $(M, A, B) = (2, 1, 1), (3, 2, 1), (4, 2, 2), (4, 2, 3), (4, 3, 1), \ldots$。

对于第 $2$ 个测试用例，不存在良好组合。

对于第 $3$ 个测试用例，良好组合按字典序依次为 $(M, A, B) = (4, -7, 39), (7, -12, 68), (8, -14, 78), (8, -14, 79), (9, -16, 89), (10, -17, 97), (11, -19, 107), \ldots$。

约束条件

• 所有输入均为整数。
• $1 \leq T \leq 1000$
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq 10^9$
• $0 \leq X_i < 2^{30}$
• 所有测试用例中的 $N$ 总和不超过 $2 \times 10^5$。

由 ChatGPT 5 翻译