AT_arc136_e.[ARC136E] Non-coprime DAG

有一个包含 $N$ 个顶点的有向图 $G$，顶点编号为 $1$ 到 $N$。

对于任意两个顶点 $i, j$（$1 \leq i, j \leq N$，$i \neq j$），当且仅当同时满足以下两个条件时，存在一条从 $i$ 到 $j$ 的有向边 $i \to j$：

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

此外，每个顶点都有一个确定的价值，顶点 $i$ 的价值为 $A_i$。

请你选择一个顶点集合 $s$，使其满足以下条件：

• 对于 $s$ 中任意两个不同的顶点对 $(x, y)$（$x < y$），在图 $G$ 上都无法从 $x$ 到 $y$ 到达。

请你求出 $s$ 中所有顶点的价值之和的最大可能值。

输入通过标准输入给出，格式如下：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

请输出答案。

限制条件

• $1 \leq N \leq 10^6$
• $1 \leq A_i \leq 10^9$
• 所有输入的值均为整数

样例解释 1

可以选择 $s = \{1, 2, 3, 5\}$。

样例解释 2

可以选择 $s = \{1, 5, 6\}$。

由 ChatGPT 4.1 翻译