P5856 「SWTR-3」Game

小 E 在玩一个数字游戏。

小 E 有 $n$ 个正整数 $a_1,a_2,\dots,a_n$。他可以进行以下操作任意次： 选择一个数 $q$，和一个集合 $S=\{d_1,d_2,\dots,d_m\}$，使得 $a_{d_1},a_{d_2},\dots,a_{d_m}$ 能被 $q$ 整除，并将 $a_{d_1},a_{d_2},\dots,a_{d_m}$ 除以 $q$。 - $q$ 要满足可以写成 $p^z$ 的形式，其中 $p$ 为质数，$z$ 为正整数。 求最少需要进行多少次操作才能将这些数变为相等的数。

无

无

#### 「样例 1 说明」 一开始的序列为 12 30 48 36 18。 选择 $S=\{4,5\},p=3$，操作后变为 12 30 48 12 6。 选择 $S=\{1,3,4\},p=2$，操作后变为 6 30 24 6 6。 选择 $S=\{2\},p=5$，操作后变为 6 6 24 6 6。 选择 $S=\{3\},p=2^2=4$，操作后变为 6 6 6 6 6。 共 4 次操作，方法不唯一。 #### 「数据范围与约定」 **本题使用捆绑测试。** Subtask 编号 | $n\leq$ | $a_i\leq$ | 特殊性质 | 得分 :-: | :-: | :-: | :-: | :-: $1$ | $8$ | $50$ | $a_i$ 中有一个数为 $1$ | $13$ $2$ | $10$ | $100$ | 无 | $17$ $3$ | $10^3$ | $10^4$ | 无 | $29$ $4$ | $10^5$ | $10^6$ | 无 | $41$ 对于 $100\%$ 的数据，有 $1\leq n\leq 10^5$，$1\leq a_i\leq 10^6$。 对于所有测试点，时间限制 1s，空间限制 128MB。 #### 「来源」 [Sweet Round 03 B](https://www.luogu.com.cn/contest/24755)。 idea & solution：ET2006 & Alex_Wei。