카드 모두 잇기

시간 제한5초메모리 제한768 MB

요약

두 카드 중 큰 수를 작은 수로 나눈 나머지를 비용으로 삼아 모든 카드를 연결할 때 전체 비용을 최소화합니다.

난이도: 어려움10점 중 8점
유형: 최소 신장 트리, 정수론, 유니온 파인드
정답자: 아직 제출이 없습니다

문제

다니엘은 사탕 한 봉지와 카드 $N$ 장을 가지고 있다. 카드마다 양의 정수 $P_i$ 가 하나씩 적혀 있다.

사탕을 먹던 다니엘은 놀이를 하나 떠올렸다. 적힌 수가 $a$ 와 $b$ 인 카드 두 장을 끈으로 묶을 수 있고, 한 번 묶을 때마다 사탕을 $\min(a \bmod b,\ b \bmod a)$ 개 먹어야 한다. $x \bmod y$ 는 $x$ 를 $y$ 로 나눈 나머지이다.

다니엘은 카드 한 장을 집어 올리면 나머지 카드가 모두 딸려 올라오도록 카드를 묶으려고 한다. 카드 한 장은 다른 카드 몇 장과도 직접 묶을 수 있다. 몸매를 신경 쓰는 다니엘은 사탕을 많이 먹고 싶지 않다.

모든 카드가 하나로 이어지도록 묶을 때 먹어야 하는 사탕 개수의 최솟값을 구하라.

입력

첫째 줄에 양의 정수 $N$ 이 주어진다. ( $1 \le N \le 10^5$ )

다음 $N$ 개의 줄에 카드에 적힌 양의 정수 $P_i$ 가 한 줄에 하나씩 주어진다. ( $1 \le P_i \le 10^7$ )

출력

모든 카드를 하나로 잇기 위해 먹어야 하는 사탕 개수의 최솟값을 첫째 줄에 출력한다.

힌트

첫 번째 예제에서 다니엘은 첫째 카드와 둘째 카드를 묶어 사탕을 0개 먹고, 둘째 카드와 셋째 카드를 묶어 0개를 먹고, 첫째 카드와 넷째 카드를 묶어 1개를 먹는다. 이렇게 하면 사탕 1개로 카드 네 장이 모두 이어진다.

예제3

예제 1
입력
```
4
2
6
3
11
```
예상 출력
```
1
```
예제 2
입력
```
4
1
2
3
4
```
예상 출력
```
0
```
예제 3
입력
```
3
4
9
15
```
예상 출력
```
4
```