一道埃筛 + 组合数学的题目。
题意：给定一个序列 $\{a\}$，执行以下的操作直到所有数相等：乘一个质数或除一个质数。求所有子序列最少操作次数的和，对 $10 ^ 9 + 7$ 取模。$n, a_i\leq 3\times 10 ^ 5$，5 s。可以加强到 $n, a_i\leq 2\times 10 ^ 7$。
容易发现每一个质数是独立的，可以分开计算贡献。另外，显然当取质数次数的中位数是最优的策略。
对每一个质数分别考虑，假设当前按质数次数降序排名为 $i$ 的数次数为 $x_i$，中位数为 $x$，那么答案为 $|x_i - x|$。
如果我们将整个展开，发现 $\dfrac n2$ 个数 $x$ 的贡献是负，$\dfrac n2$ 个数 $x$ 的贡献是正，那么我们只需要考虑 $x_i$ 的贡献。
假设排名小于 $i$ 的选了 $a$ 个（$0\leq a< i$），大于 $i$ 的选了 $b$ 个（$0\leq b< n - i + 1$），那么根据 $a$ 和 $b$ 的大小可以分为：
- $a < b$，则 $x_i$ 贡献为正。
- $a = b$，则 $x_i$ 贡献为 0。
- $a > b$，则 $x_i$ 贡献为负。
$a, b$ 的相对关系看起来不好枚举，我们换做 $i - 1 - a + b$ 与 $i - 1$ 的大小关系可能更好枚举。于是我们可以得到下面的式子：
我们可以预处理 $f(k) = \sum_{i = k}^{n - 1} \binom{n - 1}i - \sum_{i = 0}^{k - 2}\binom{n - 1}i$，可能会更好求。
发现 $x_i$ 一样的段，贡献是连续的，也就是 $f(k)$ 是一段的和。假设枚举次幂 $t$，设 $x_i\geq t$ 的个数为 $a$，$x_i > t$ 的个数为 $b$，那么 $t$ 的贡献就是：
再次前缀和 $g(i) = \sum_{j = 1} ^ i f(j)$，那么这个贡献也可以 $O(1)$ 计算。那么瓶颈在于计算 $x_i\geq t$ 的个数。这个可以通过埃筛来计算。
具体来说，我们直接考虑枚举质数 $p$，然后对于他的次幂，暴力计算次幂的倍数有多少个。据说时间复杂度是 $O(n\log\log n)$ 的，实测 $4\times 10 ^ 7$ 也只要 0.5s（不算读入）。有好心人发一下证明吗？
代码比较简短。放一个主函数。
1 | pre[0] = 1; |