配点 : 100 点
問題文
整数 N,K 和长度 N 整数序列 给出了 X=(X_0,X_1,\ldots,X_{N-1}) 。
满足以下所有条件的一组整数 (M,A,B) 输出为好团体。
- 1 \le M < 2^{30}
- k=0,1,\ldots,N-1 反对 \displaystyle X_k = \left\lfloor\frac{Ak+B}M \right\rfloor 成立。
可以证明,在约束条件下,好对的数量是有限的。这个号码 确定 C 。 当
K \le C 是否成立,如果成立,则使用字典顺序。 找到 K 最小的好对。 您将获得
T 测试用例,因此请逐一回答。
制約
- 所有输入均为整数
- 1\le T \le 1000
- 2\le N \le 2\times 10^5
- 1\le K\le 10^9
- 0\le X_i < 2^{30}
- 在所有测试用例中 N 的总和是 2\times 10^5 以下
部分点
- 附加限制 如果正确答案是满足 K=1 的数据集 如果正确答案是满足 2 点。
- 附加限制 如果正确答案是满足 K\le 10 的数据集,则进一步 18 点。
入力
输入将以以下形式从标准输入给出。
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 行中, \text{case}_i 关于 K \le C 成立,则顺序是按字典顺序排列的。 K 最小的好对 M,A,B 按照这个顺序,用半角空格分隔,如果不成立,
对于第 -1 。
入力例 1
3 4 1 0 1 1 2 3 1 2 0 1 6 7 9 8 6 4 2 1
出力例 1
2 1 1 -1 11 -19 107
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 。