/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
N 頂点からなる有向グラフ G があり，頂点には 1 から N までの番号がついています．
二つの頂点 i,j (1 \leq i,j \leq N, i \neq j) の間には，以下の条件を両方満たす時，またその時のみ，辺 i \to j が存在します．
- i<j
- \mathrm{gcd}(i,j)>1
また，各頂点にはそれぞれ価値が定まっており，頂点 i の価値は A_i です．
以下の条件を満たすように頂点の集合 s を選ぶことを考えます．
- s に含まれるどの二つの異なる頂点の組 (x,y) (x<y) についても，G 上で x から y には到達できない．
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
Score : 800 points
Problem Statement
We have a directed graph G with N vertices numbered 1 to N.
Between two vertices i,j (1 \leq i,j \leq N, i \neq j), there is an edge i \to j if and only if both of the following conditions are satisfied.
- i<j
- \mathrm{gcd}(i,j)>1
Additionally, each vertex has an associated value: the value of Vertex i is A_i.
Consider choosing a set s of vertices so that the following condition is satisfied.
- For every pair (x,y) (x<y) of different vertices in s, y is unreachable from x in G.
Find the maximum possible total value of vertices in s.
Constraints
- 1 \leq N \leq 10^6
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
Print the answer.
Sample Input 1
6 1 1 1 1 1 1
Sample Output 1
4
We should choose s=\{1,2,3,5\}.
Sample Input 2
6 1 2 1 3 1 6
Sample Output 2
8
We should choose s=\{1,5,6\}.
Sample Input 3
20 40 39 31 54 27 31 80 3 62 66 15 72 21 38 74 49 15 24 44 3
Sample Output 3
343