107 . NewWorld Online

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

88.9% (8/9)

Submission's AC Ratio

88.9% (8/9)

Tags

ioicamp ioicamp-2023

Description

NewWorld Online 的魔寵系統就快要開放了！大家都迫不及待要收服可愛的小動物當成自己的夥伴。但是管理員們十分緊張，他們擔心會有許多人騎著烏龜飛來飛去，釀成危險的空中車禍，所以管理員們決定在一些景點之間建立好安全的通道。

第七階一共有 $N$ 個特別的景點，每個景點都有一種特殊的地形，地形可以用一個正整數來表示。管理員準備了 $10^ 6$ 種打造通道的建材，建材的強度分別是 $1$ 到 $10^ 6$ 的正整數，每一種建材的數量都足夠建造任意條通道。每一條通道會用同一種建材連接兩個不同的景點，但是為了適應景點的地形，建材的強度必須是兩端景點地形的公因數。為了建造一個方便又安全的場景，管理員們希望任兩個景點都能互相到達，而且不要形成環狀的路徑，以免有玩家迷路。

管理員希望建造的通道能堅固一點，可是他們忙著看梅普露賣萌，沒空處理遊戲環境，所以決定找你幫忙。請你規劃一個蓋通道的方式，並告訴他們建材強度的總和最大可以有多少。

Input Format

輸入第一行包含一個正整數 $N$，代表景點的數量。

第二行包含 $N$ 個整數 $a_1, a_2, \ldots, a_N$，代表第 $i$ 個景點的地形。

  • $1 \leq N \leq 10^ 5$
  • $1 \leq a_i \leq 10^ 6$

Output Format

輸出一個正整數代表建材強度的總和的最大值。一種建材使用多次時強度也會以多倍計算。

Sample Input 1

4
2 4 8 16

Sample Output 1

14

Sample Input 2

5
34 38 25 11 49

Sample Output 2

5

Hints

Problem Source

IOICamp 2023 Day2 pG

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~22 $N \leq 2000$ 30
3 0~48 無其他限制 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 524288 65536 1 2 3
1 4000 524288 65536 1 2 3
2 4000 524288 65536 2 3
3 4000 524288 65536 2 3
4 4000 524288 65536 2 3
5 4000 524288 65536 2 3
6 4000 524288 65536 2 3
7 4000 524288 65536 2 3
8 4000 524288 65536 2 3
9 4000 524288 65536 2 3
10 4000 524288 65536 2 3
11 4000 524288 65536 2 3
12 4000 524288 65536 2 3
13 4000 524288 65536 2 3
14 4000 524288 65536 2 3
15 4000 524288 65536 2 3
16 4000 524288 65536 2 3
17 4000 524288 65536 2 3
18 4000 524288 65536 2 3
19 4000 524288 65536 2 3
20 4000 524288 65536 2 3
21 4000 524288 65536 2 3
22 4000 524288 65536 2 3
23 4000 524288 65536 3
24 4000 524288 65536 3
25 4000 524288 65536 3
26 4000 524288 65536 3
27 4000 524288 65536 3
28 4000 524288 65536 3
29 4000 524288 65536 3
30 4000 524288 65536 3
31 4000 524288 65536 3
32 4000 524288 65536 3
33 4000 524288 65536 3
34 4000 524288 65536 3
35 4000 524288 65536 3
36 4000 524288 65536 3
37 4000 524288 65536 3
38 4000 524288 65536 3
39 4000 524288 65536 3
40 4000 524288 65536 3
41 4000 524288 65536 3
42 4000 524288 65536 3
43 4000 524288 65536 3
44 4000 524288 65536 3
45 4000 524288 65536 3
46 4000 524288 65536 3
47 4000 524288 65536 3
48 4000 524288 65536 3
Submit
Back to Top