COCI 2016/2017 - Contest 6 - Sirni
View as PDFDaniel có một túi kẹo và ~N~ tấm thẻ.
Trên tấm thẻ thứ ~i~ có một số nguyên dương ~P_i~. Khi Daniel đang ăn kẹo, cậu nghĩ ra một trò chơi thú vị. Cậu có thể gắn một cặp thẻ gồm ~1~ tấm thẻ thứ ~a~ và ~1~ tấm thẻ thứ ~b~ lại với nhau, sau đó ăn ~min~ ~(P_a \% P_b~ ~,~ ~P_b \% P_a)~ cái kẹo, trong đó ~x\%y~ là số dư của phép chia ~x~ cho ~y~.
Daniel muốn gắn các tấm thẻ vào nhau sao cho khi cậu nhấc một trong số chúng lên, tất cả các tấm thẻ còn lại cũng được nhấc lên. Mỗi tấm thẻ có thể được gắn trực tiếp với một số lượng bất kỳ các tấm thẻ khác. Daniel đang giảm cân nên không muốn ăn quá nhiều kẹo, vì vậy Daniel muốn nhờ bạn tìm ra số kẹo ít nhất phải ăn để tất cả các tấm thẻ được gắn với nhau thỏa mãn điều kiện nêu trên.
Input
Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 10^5)~
~N~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên dương ~P_i~ ~(1 \le P_i \le 10^7)~.
Output
In ra số nguyên duy nhất là số kẹo ít nhất cần ăn.
Sample 1
Input
4
2
6
3
11
Output
1
Giải thích
Daniel có thể gắn hai thẻ đầu tiên và ăn ~0~ cái kẹo, gắn thẻ thứ hai với thẻ thứ ba và ăn ~0~ cái kẹo, gắn thẻ đầu tiên với thẻ cuối cùng và ăn ~1~ cái kẹo.
Sample 2
Input
4
1
2
3
4
Output
0
Sample 3
Input
3
4
9
15
Output
4
Subtask
- ~9~ test đầu có ~N \le 10^3~
- ~12~ test tiếp theo có ~P_i \le 10^6~
- ~9~ test còn lại không có điều kiện gì thêm
Comments
This comment is hidden due to too much negative feedback. Show it anyway.