COCI '16 Contest 6 #5 Sirni

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 5.0s
Memory limit: 768M

Problem types

Little Daniel has a bag of candy and N cards.

Each of the cards has a positive integer P_i written on it. While Daniel was eating his candy, he thought of a fun game. He can tie together two cards with labels a and b, and then he must eat \min(P_a \mathbin{\%} P_b, P_b \mathbin{\%} P_a) of candy, where operation x \mathbin{\%} y denotes the remainder when dividing x with y.

He wants to tie together pairs of cards in a way that, when he lifts one of them, all the rest are also lifted up. Each card can be directly connected with a tie to any number of other cards. As Daniel is watching his figure, he doesn't want to consume too much, so he is asking you to calculate the minimal number of candy he must eat so all cards are connected.

Input Specification

The first line of input contains the positive integer N (1 \le N \le 10^5).

Each of the following N lines contains a positive integer P_i (1 \le P_i \le 10^7).

Output Specification

The first and only line of output must contain the required value from the task.

Scoring

In test cases worth 30\% of total points, it will hold N \le 10^3.

In test cases worth 40\% of total points, it will hold P_i \le 10^6.

In test cases worth 70\% of total points, at least one of the two conditions will hold.

Sample Input 1

4
2
6
3
11

Sample Output 1

1

Explanation for Sample Output 1

Daniel can connect the first and second card and eat 0 candy, the second and third and eat 0 candy, and the first and fourth and eat 1 candy.

Sample Input 2

4
1
2
3
4

Sample Output 2

0

Sample Input 3

3
4
9
15

Sample Output 3

4

Comments

There are no comments at the moment.