#CF2266E. Prime Destruction
Prime Destruction
题目描述
给定一个由 个正整数组成的多重集合 。
你可以执行以下操作任意次(可以为零次):
- 从多重集合中选择一个大于 的整数 及 的一个质因数 。从多重集合中移除一个 ,并加入 个 。
另外给定一个整数 ()。令 为从原始多重集合出发,使得多重集合中每个整数都不超过 所需的最少操作次数。
求 。
输入格式
每个测试包含多组测试数据。第一行包含测试数据组数 ()。接下来是每组测试数据的描述。
每组测试数据的第一行包含两个整数 和 (),分别表示多重集合的初始大小和给定整数。
每组测试数据的第二行包含 个整数 (),表示多重集合的元素。
保证所有测试数据的 之和不超过 。
输出格式
对于每组测试数据,输出一个整数 。
样例
6
1 1
1
6 2
6 6 4 3 2 1
8 1
8 6 4 3 2 1 8 6
12 3
12 10 9 8 7 6 5 4 3 2 1 12
10 9
10 9 8 7 6 5 4 3 2 1
5 5
5 4 3 2 1
0
4
25
15
1
0
说明
在第一组测试数据中,唯一的元素已经不超过 ,因此不需要任何操作。
在第二组测试数据中,我们可以执行以下操作:
$[\color{red}{6},6,4,3,2,1] \rightarrow [\color{red}{2,2,2},6,4,3,2,1]$,
$[2,2,2,\color{red}{6},4,3,2,1] \rightarrow [2,2,2,\color{red}{2,2,2},4,3,2,1]$,
$[2,2,2,2,2,2,\color{red}{4},3,2,1] \rightarrow [2,2,2,2,2,2,\color{red}{2,2},3,2,1]$,
$[2,2,2,2,2,2,2,2,\color{red}{3},2,1] \rightarrow [2,2,2,2,2,2,2,2,\color{red}{1,1,1},2,1]$。
因此, 次操作即可。可以证明不存在操作次数严格更少的方案。
来源
来自 Codeforces — Codeforces Round 1122 (Div. 3)。