← 返回题目列表

AtCoder · utpc2025_l

L. 线性地板

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

配点 : 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 。