CF653G Move by Prime

猫咪 Sonya 有一个包含 $n$ 个正整数的数组。该数组共有 $2^n$ 个可能的子序列。对于每一个子序列，她都会计算将其中所有元素变为相等所需的最小操作次数。每次操作有两种方式： - 选择子序列中的一个元素，将其乘以某个质数。 - 选择子序列中的一个元素，将其除以某个质数（被选择的元素必须能被该质数整除）。 求所有 $2^n$ 个子序列的最小操作次数之和。请将答案对 $10^{9}+7$ 取模后输出。

第一行包含一个整数 $n$，表示数组的大小（$1 \leq n \leq 300000$）。 第二行包含 $n$ 个整数 $t_1, t_2, \ldots, t_n$，表示数组的各个元素（$1 \leq t_i \leq 300000$）。

输出所有可能子序列的最小操作次数之和，对 $10^{9}+7$ 取模。

在第一个样例中，总共存在 $8$ 个子序列：$(60,60,40)$，$(60,60)$，$(60,40)$，$(60,40)$，$(60)$，$(60)$，$(40)$ 和空子序列 $()$。 对于子序列 $(60,60,40)$，我们可以通过两步操作使所有元素相等——先将 $40$ 除以 $2$ 得到 $20$，然后将 $20$ 乘以 $3$ 得到 $60$。这已经是最少的操作次数，因此我们将 $2$ 加入答案。 有两个子序列等于 $(60,40)$，对于每一个同样也需要至少 $2$ 次操作。 其他各个子序列中的数字已经全部相等，因此每个所需的操作次数为 $0$。总和为 $2+2+2=6$。 由 ChatGPT 5 翻译