問題一覧 > 通常問題

No.3270 No Coprime Cycles

レベル : / AI推定難易度 : 2500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 18
作問者 : apricity / テスター : 👑 qand
お気に入りにしたユーザー ProblemId : 12469 / 自分の提出
問題文最終更新日: 2025-09-10 19:13:53
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 482 (順位表) の他の問題:

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.

  1. Initialize $g(B)$ as a graph with $|B|$ vertices, numbered from vertex $1$ to vertex $|B|$, and $0$ edges.
  2. 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$.
Find the minimum possible total cost required to achieve this goal.

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})$
Since cycles such as the following exist, $A = (6,6,12)$ does not satisfy the condition.
  • 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$.
For the resulting $A = (3,3,12)$, the only cycle in $g(A)$ consists of the $3$ edges $(1,2,{\color{red}3}), (2,3,{\color{red}3}), (1,3,{\color{red}3})$. Since all the labels are divisible by $3$, $A = (3,3,12)$ satisfies the condition.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。