← 返回题目列表

AtCoder · arc136_e

E. 非互质 DAG

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

分数: 800 点

问题陈述

我们有一个有向图 G 与 N 顶点编号 1 to N.

两个顶点之间 i,j (1 \leq i,j \leq N, i \neq j),有一个边缘 i \to j 当且仅当满足以下两个条件时。

  • i<j
  • \mathrm{gcd}(i,j)>1

此外,每个顶点都有一个关联值:Vertex 的值 i is A_i.

考虑选择一套 s 的顶点,以满足以下条件。

  • 对于每对 (x,y) (x<y) 中的不同顶点 无法从以下位置访问 s, y 无法从以下位置到达 x in G.

找到以下顶点的最大可能总值 s.

约束

  • 1 \leq N \leq 10^6
  • 1 \leq A_i \leq 10^9
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \cdots A_N

输出

打印答案。


示例输入 1

6
1 1 1 1 1 1

示例输出 1

4

我们应该选择 s=\{1,2,3,5\}.


示例输入 2

6
1 2 1 3 1 6

示例输出 2

8

我们应该选择 s=\{1,5,6\}.


示例输入 3

20
40 39 31 54 27 31 80 3 62 66 15 72 21 38 74 49 15 24 44 3

示例输出 3

343