201364: [AtCoder]ARC136 E - Non-coprime DAG
Memory Limit:1024 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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