← 返回题目列表

Codeforces · 1292/D

D. 混乱 V。

中文机器翻译题面 查看原题

“一切都已经计划好了,不再有隐忧。Cytus的状况也很完美。

现在时间……00:01:12……

时间到了。”

情绪样本现在已经足够了。近三年过去了,艾薇是时候唤醒她亲密的妹妹凡妮莎了。

A.R.C. 库核心内的系统可以被视为具有无限数量处理节点的无向​​图,所有节点均以正整数编号($$$1, 2, 3, \ldots$$$)。编号为 $$$x$$$ ($$$x > 1$$$) 的节点直接与编号为 $$$\frac{x}{f(x)}$$$ 的节点相连,其中 $$$f(x)$$$ 是 $$$x$$$ 的最低素因数。

Vanessa 的思维被分成 $$$n$$$ 碎片。由于昏迷超过 500 年,碎片已经分散:第 $$$i$$$ 碎片现在位于编号为 $$$k_i!$$$ 的节点($$$k_i$$$ 的阶乘)。

为了最大化成功唤醒的机会,Ivy决定将样本放置在节点$$$P$$$中,使得从每个片段到$$$P$$$的路径总长度尽可能最小。如果同一节点有多个分片,则需要多次统计从该节点到$$$P$$$的路径。

在零和一的世界里,这样的要求对于Ivy来说非常简单。不到一秒的时间,她就已经想通了这样一个节点。

但是对于你这样一个普通人来说,这还有可能吗?

为简单起见,请回答从每个片段到情感样本的组装节点 $$$P$$$ 的路径长度的最小总和。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — Vanessa 心灵碎片的数量。

第二行包含$$$n$$$整数:$$$k_1, k_2, \ldots, k_n$$$ ($$$0 \le k_i \le 5000$$$),表示Vanessa心灵碎片所在的节点:第$$$i$$$个碎片位于编号为$$$k_i!$$$的节点。

输出

打印一个整数,表示从每个片段到具有情感样本的节点(也称为节点 $$$P$$$)的最小路径总和。

提醒一下,如果同一节点有多个片段,则该节点到 $$$P$$$ 的距离也需要多次计算。

示例

输入 #1

3
2 1 4

输出 #1

5

输入 #2

4
3 1 4 4

输出 #2

6

输入 #3

4
3 1 4 1

输出 #3

6

输入#4

5
3 1 4 1 5

输出#4

11

注意

考虑到系统的前 $$$24$$$ 节点,节点网络将如下所示(节点 $$$1!$$$、$$$2!$$$、$$$3!$$$、$$$4!$$$ 以粗体绘制):

对于第一个示例,Ivy 会将情绪样本放置在节点 $$$1$$$ 处。从这里开始:

- 从 Vanessa 的第一个片段到节点 $$$1$$$ 的距离是 $$$1$$$。
- 从 Vanessa 的第二个片段到节点 $$$1$$$ 的距离是 $$$0$$$。
- 从 Vanessa 的第三个碎片到节点 $$$1$$$ 的距离是 $$$4$$$。

总长度为$$$5$$$。

对于第二个示例,装配节点将为 $$$6$$$。从这里开始:

- 从 Vanessa 的第一个片段到节点 $$$6$$$ 的距离是 $$$0$$$。
- 从 Vanessa 的第二个片段到节点 $$$6$$$ 的距离是 $$$2$$$。
- 从 Vanessa 的第三个碎片到节点 $$$6$$$ 的距离是 $$$2$$$。
- 从 Vanessa 的第四个碎片到节点 $$$6$$$ 的距离又是 $$$2$$$。

总路径长度为 $$$6$$$。