No.3270 No Coprime Cycles
Problem Statement
For a sequence of positive integers $B = (B_1,B_2,\dots,B_{|B|})$, let $g(B)$ denote the undirected graph with edges labeled by positive integers, constructed by the following procedure.
- Initialize $g(B)$ as a graph with $|B|$ vertices, numbered from vertex $1$ to vertex $|B|$, and $0$ edges.
- For every pair of integers $(i, j)$ satisfying $1 \le i < j \le |B|$, do the following.
- Let $S_{ij}$ be the set of all common divisors of $B_i$ and $B_j$ that are $\bm{2}$ or greater. For every element $d$ of $S_{ij}$, add to $g(B)$ an undirected edge with label $d$ connecting vertex $i$ and vertex $j$.
You are given a sequence of positive integers $A = (A_1,A_2,\dots,A_N)$ of length $N$. You may perform the following operation on $A$ any number of times, possibly $0$ times.
- Choose an integer $i$ satisfying $1 \le i \le N$ and a positive divisor $x$ of $A_i$, and replace $A_i$ with $\dfrac{A_i}{x}$. This operation costs $x$.
Your goal is to make $A$ satisfy the following condition.
- There does not exist a cycle in $g(A)$ of length $\bm{2}$ or more such that the largest positive integer dividing the labels of all edges forming the cycle is $1$.
Input
$N$ $A_1\ A_2\ \dots\ A_N$
- All input values are integers.
- $2 \le N \le 2 \times 10^5$
- $1 \le A_i \le 10^6$
Output
Output the minimum possible total cost required to achieve the goal.
Sample
Sample 1
Input
3 6 6 12
Output
4
Let $(i,j,{\color{red}d})$ denote an edge with label $\color{red}d$ connecting vertex $i$ and vertex $j$. For $A = (6,6,12)$, the edges in $g(A)$ are as follows.
- $(1,2,{\color{red}2})$
- $(1,2,{\color{red}3})$
- $(1,2,{\color{red}6})$
- $(1,3,{\color{red}2})$
- $(1,3,{\color{red}3})$
- $(1,3,{\color{red}6})$
- $(2,3,{\color{red}2})$
- $(2,3,{\color{red}3})$
- $(2,3,{\color{red}6})$
- The cycle of length $3$ formed by the edges $(1,2,{\color{red}2}), (2,3,{\color{red}3}), (1,3,{\color{red}6})$. The largest positive integer dividing $2,3,6$ is $1$.
- The cycle of length $2$ formed by the edges $(1,2,{\color{red}2}), (1,2,{\color{red}3})$. The largest positive integer dividing $2,3$ is $1$.
The following operations satisfy the condition at a cost of $4$.
- Choose $i = 1$, $x = 2$, making $A_1 \leftarrow 3$.
- Choose $i = 2$, $x = 2$, making $A_2 \leftarrow 3$.
Sample 2
Input
4 1 2 4 8
Output
0
$A = (1,2,4,8)$ satisfies the condition, so no operations need to be performed.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
apricity