P13061 [GCJ 2020 #1C] Oversized Pancake Choppers

当你作为"无限煎饼屋"的主厨刚上班时，又一次发现灾难现场！其他厨师不小心做出了一些巨大的圆形煎饼，且所有煎饼大小相同。这些煎饼太大无法整块供应，于是他们已经开始将煎饼切成扇形切片（在本问题中即为圆形扇形）。你现在有 $\mathbf{N}$ 块切片，其中第 $i$ 块是中心角为 $\mathbf{A}_i$ 纳度（1 纳度 = $10^{-9}$ 度）的扇形。 现在有 $\mathbf{D}$ 位顾客等待用餐。每位顾客需要**一块**与其他顾客**大小完全相同**的切片（具体大小不限）。但现有切片可能无法满足需求，因此你可能需要进行若干次径向切割。 一次切割操作可以将一个中心角为 $X$ 的切片分成两个新切片，其中心角分别为 $Y$ 和 $X - Y$。其中 $0 < Y < X$ 且不需要为整数。你可以对这两个新切片继续切割，以此类推。 允许存在任意大小的剩余切片（不供应给顾客）——毕竟这场灾难让你错过了早餐！ 请计算满足顾客需求所需的最少切割次数。

输入第一行包含测试用例数量 $\mathbf{T}$。随后每个测试用例包含： - 第一行：两个整数 $\mathbf{N}$（现有切片数）和 $\mathbf{D}$（顾客数） - 第二行：$\mathbf{N}$ 个整数 $\mathbf{A}_1, \mathbf{A}_2, ..., \mathbf{A}_\mathbf{N}$，表示每块切片的中心角（纳度）

对于每个测试用例，输出一行 `Case #x: y`，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为所需的最少切割次数。

**样例解释** 样例 #1：初始只有 1 块极小切片。最优方案是： 1. 第一次切割得到 $1/3$ 纳度和 $2/3$ 纳度的切片 2. 将后者再次切割为两块 $1/3$ 纳度的切片 最终得到 3 块相同切片，共需 2 次切割。 样例 #2：已有两块相同大小的切片可直接供应，无需切割。 样例 #3：最优方案是将 8 纳度的切片对半切割，得到 3 块 4 纳度的切片且无剩余。 样例 #4：注意每位顾客必须获得**单块**切片。即使 "1+2" 和 "3" 的总面积相同，也不符合要求。此时至少需要进行 1 次切割。 **数据范围** - $1 \leq T \leq 100$ - $1 \leq A_i < 360 \times 10^9$（所有 $i$） **测试集 1（10 分，可见判定）** - 时间限制：20 秒 - $1 \leq N \leq 300$ - $2 \leq D \leq 3$ **测试集 2（16 分，可见判定）** - 时间限制：20 秒 - $1 \leq N \leq 300$ - $2 \leq D \leq 50$ **测试集 3（16 分，隐藏判定）** - 时间限制：60 秒 - 其中 21 个用例满足 $9000 \leq N \leq 10000$ - 其余 $T-21$ 个用例满足 $1 \leq N \leq 1000$ - $2 \leq D \leq 50$ 翻译由 DeepSeek V3 完成