#CF2266E. Prime Destruction

Prime Destruction

题目描述

给定一个由 nn 个正整数组成的多重集合 aa。

你可以执行以下操作任意次(可以为零次):

  • 从多重集合中选择一个大于 11 的整数 xx 及 xx 的一个质因数 pp。从多重集合中移除一个 xx,并加入 pp 个 xp\frac{x}{p}。

另外给定一个整数 kk(1≤k≤n1 \le k \le n)。令 f(k)f(k) 为从原始多重集合出发,使得多重集合中每个整数都不超过 kk 所需的最少操作次数。

求 f(k)f(k)。

输入格式

每个测试包含多组测试数据。第一行包含测试数据组数 tt(1≤t≤1041 \le t \le 10^4)。接下来是每组测试数据的描述。

每组测试数据的第一行包含两个整数 nn 和 kk(1≤k≤n≤2⋅1051 \le k \le n \le 2 \cdot 10^5),分别表示多重集合的初始大小和给定整数。

每组测试数据的第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n(1≤ai≤n1 \le a_i \le n),表示多重集合的元素。

保证所有测试数据的 nn 之和不超过 2⋅1052 \cdot 10^5。

输出格式

对于每组测试数据,输出一个整数 f(k)f(k)。

样例

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

说明

在第一组测试数据中,唯一的元素已经不超过 kk,因此不需要任何操作。

在第二组测试数据中,我们可以执行以下操作:

$[\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]$。

因此,44 次操作即可。可以证明不存在操作次数严格更少的方案。

来源

来自 Codeforces — Codeforces Round 1122 (Div. 3)。