“一切都已经计划好了,不再有隐忧。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$$$。