CF653G

一道埃筛 + 组合数学的题目。

题意：给定一个序列 ${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 |$ 。

如果我们将整个展开，发现 $\frac{n}{2}$ 个数 $x$ 的贡献是负， $\frac{n}{2}$ 个数 $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$ 的大小关系可能更好枚举。于是我们可以得到下面的式子：

\sum_{j = i}^{n - 1} (\binom{n - 1}{j}) - \sum_{j = 0}^{i - 2} (\binom{n - 1}{j})

我们可以预处理 $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$ 的贡献就是：

t \sum_{i = b + 1}^{a} f (i)

再次前缀和 $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（不算读入）。有好心人发一下证明吗？

代码比较简短。放一个主函数。

pre[0] = 1;
for (int j = 1; j < n; ++ j) adj(pre[j] = pre[j - 1] + C(n - 1, j) - Mod);
for (int i = 1, tmp; i <= n; ++ i)
	adj(ans[i] = ans[i - 1] + adj(adj(tmp = pre[n - 1] - pre[i - 1]) -= (i == 1 ? 0 : pre[i - 2])) - Mod);

int res = 0;
for (int i = 2, j; i <= mx; ++ i) {
	if (st[i]) continue;
	for (j = i << 1; j <= mx; j += i) st[j] = true;
	LL k = i;
	for (cntp[j = 1] = 0; k <= mx; cntp[++ j] = 0, k *= i)
		for (int l = k; l <= mx; l += k) cntp[j] += cnt[l];
	for (int l = j - 1, tmp; l; -- l)
		res = (res + (LL)adj(tmp = ans[cntp[l]] - ans[cntp[l + 1]]) * l) % Mod;
}