← 返回题目列表

AtCoder · arc210_c

C. 公平硬币分区

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

分数: 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.