分数: 700 点
问题陈述
有 N 硬币类型。对于 0\leq i\leq N-1, (1+i)第一种硬币的价值为 10^{i},并且您拥有 这些硬币的 A_i 。
您已决定将这些硬币分发给 M 人。但是,分配给每个人的硬币总价值必须相等。允许有未分发的硬币。
找出分配给每个人的硬币的最大可能总价值。
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1\leq T\leq 10^5
- 1\leq N\leq 2\times 10^5
- 1\leq M\leq 10^9
- 0\leq A_i\leq 10^9
- 总和 N 所有测试用例最多 2\times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出:
N M
A_0 A_1 \ldots A_{N-1}
输出
输出分配给每个人的最大可能的硬币总价值。
示例输入 1
5 3 1 123 456 789 3 1000 123 456 789 2 3 6 14 2 3 11 14 30 4 15 9 2 66 23 2 4 1 1 32 4 80 9 10 47 14 8 7 3 16 2 39 77 4 4 2 38 64 1 2
示例输出 1
83583 0 42 50 19401302040124704218001124023
- 对于第一个测试用例,如果将所有硬币分配给一个人,则分配给每个人的硬币总价值为 123\times 10^0+456\times 10^1+789\times 10^2=83583.
- 对于第二个测试用例,别无选择,只能分发 0 给大家硬币。
- 对于第三个测试用例,可以得出分配给每个人的硬币的总价值 42 如下:
- 至 1-st 人,分发 2 有价硬币 10^0 和 4 有价硬币 10^1.
- 至 2-nd 人,分发 2 有价硬币 10^0 和 4 有价硬币 10^1.
- 至 3-rd人,分发 2 有价硬币 10^0 和 4 有价硬币 10^1.
- 对于第四个测试用例,可以得出分配给每个人的硬币总价值 50 如下:
- 至 1-st 人,分发 0 有价硬币 10^0 和 5 有价硬币 10^1.
- 至 2-nd 人,分发 0 有价硬币 10^0 和 5 有价硬币 10^1.
- 至 3-rd人,分发 10 有价硬币 10^0 和 4 有价硬币 10^1.