F. GCD 最大生成树

AtCoder Beginner Contest 469

GCD 最大生成树

GCD Maximum Spanning Tree

AtCoder

⌀ 1567

原题

← CG →

GCD 最大生成树AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

You are given a sequence of positive integers $A$ of length $N$ . There is a weighted complete undirected graph with $N$ vertices. The vertices are numbered $1,2,\dots,N$ . For $i$ and $j$ satisfying $1 \leq i \lt j \leq N$ , the weight of the edge connecting vertices $i$ and $j$ is the greatest common divisor of $A_i$ and $A_j$ . Find the maximum possible value of the sum of the weights of the edges included in a spanning tree of this graph.

给定一个长度为 $N$ 的正整数序列 $A$ 。有一个包含 $N$ 个顶点的带权无向完全图，顶点编号为 $1,2,\dots,N$ 。对于满足 $1 \leq i \lt j \leq N$ 的 $i$ 和 $j$ ，连接顶点 $i$ 和顶点 $j$ 的边的权值为 $A_i$ 和 $A_j$ 的最大公约数。求该图的一棵生成树所包含的边的权值和的最大可能值。AI (CI翻译)

Constraints

约束条件

AI (CI翻译)

$2 \leq N \leq 2 \times 10^5$
$1 \leq A_1 \lt A_2 \lt \dots \lt A_N \leq 10^6$
All input values are integers.

$2 \leq N \leq 2 \times 10^5$
$1 \leq A_1 \lt A_2 \lt \dots \lt A_N \leq 10^6$
所有输入值均为整数。

AI (CI翻译)

Input

输入格式

AI (CI翻译)

The input is given from Standard Input in the following format:

输入从标准输入按以下格式给出：AI (CI翻译)

N
A_1 A_2 \dots A_N

N
A_1 A_2 \dots A_N

AI (CI翻译)

Output

输出格式

AI (CI翻译)

Output the answer in one line.

在一行中输出答案。AI (CI翻译)

样例

Input #1

3
4 6 12

Output #1

The complete graph has the following three edges. - The edge connecting vertices $1$ and $2$ with weight $2$ - The edge connecting vertices $1$ and $3$ with weight $4$ - The edge connecting vertices $2$ and $3$ with weight $6$ Choosing the second and third edges gives a sum of weights of $10$, which is the maximum possible value.

Input #2

5
5 14 15 21 42

Output #2

Input #3

2
1 1000000

Output #3

题目信息

题号

abc469_f

所属比赛

AtCoder Beginner Contest 469

时间限制

2 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。