{"problem":{"name":"Non-coprime DAG","description":{"content":"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 condit","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc136_e"},"statements":[{"statement_type":"Markdown","content":"We have a directed graph $G$ with $N$ vertices numbered $1$ to $N$.\nBetween 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.\n\n*   $i<j$\n*   $\\mathrm{gcd}(i,j)>1$\n\nAdditionally, each vertex has an associated value: the value of Vertex $i$ is $A_i$.\nConsider choosing a set $s$ of vertices so that the following condition is satisfied.\n\n*   For every pair $(x,y)$ ($x<y$) of different vertices in $s$, $y$ is unreachable from $x$ in $G$.\n\nFind the maximum possible total value of vertices in $s$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^6$\n*   $1 \\leq A_i \\leq 10^9$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc136_e","tags":[],"sample_group":[["6\n1 1 1 1 1 1","4\n\nWe should choose $s={1,2,3,5}$."],["6\n1 2 1 3 1 6","8\n\nWe should choose $s={1,5,6}$."],["20\n40 39 31 54 27 31 80 3 62 66 15 72 21 38 74 49 15 24 44 3","343"]],"created_at":"2026-03-03 11:01:13"}}