Informatica Online Judge

  목걸이 만들기 [1810 / 0712]

Time Limit(Test case) : 3000(ms)
Number of users who solved : 12   Total Tried : 16


The Champion of this Problem (C++) : gs17018 - ms / 763byte
My Best Submission (C++) : N/A

[koistudy.net (34st 노규민)]

Background

규민이는 n개의 보석으로 목걸이를 만들고 있다.

각 보석에는 숫자가 적혀있고, 돈 1원을 내면 그 보석에 적힌 숫자를 1 늘리거나 줄일 수 있다. 단, 보석에 적힌 숫자는 항상 자연수여야 한다.

규민이가 사는 세상에서는 서로소인 자연수 쌍을 아름답게 여긴다.

그래서 규민이는 n개의 보석 각각에 적힌 숫자 중 임의로 두 개를 고르면, 그 두 보석에 적힌 숫자가 서로소이도록 하고 싶다.

하지만 규민이는 금수저가 아니므로, 가장 돈을 적게 내고 목표를 달성하고 싶다.

Input

보석의 개수 n이 첫째 줄에 입력된다. 1<=n<=100
둘째 줄부터, 각 보석에 적힌 숫자 $a_1, a_2, ... a_n$이 입력된다.

[입력값의 정의역]

$1<=n<=100$
$1<=a_i<=30$

Output

규민이가 지불해야 할 최소 비용을 출력한다. 만약 돈을 안 써도 되면, 0을 출력한다.

IO Example

입력
5
1 1 1 1 1

출력
0

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]