| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 108 | 44 | 37 | 42.529% |
Toruń has been known for its traditional gingerbread since the Middle Ages. Young Nicolaus would like to buy a set of $n$ boxes with gingerbread cookies in his favourite shop. The shop has very strict rules, though: Nicolaus initially obtains n boxes that are already filled with cookies: the $i$-th box initially contains $a_i$ of them. Then, Nicolaus can order some extra cookies. He adds extra cookies to some boxes so that the greatest common divisor$^∗$ of the numbers of cookies in all of the boxes becomes equal to 1ドル$. It can be proven that this is always possible.
Help Nicolaus by calculating the smallest number of cookies that need to be added in order to make the greatest common divisor of all the numbers equal to 1ドル$.
$^∗$The greatest common divisor (GCD) of multiple numbers is the largest positive integer that divides all of them without remainder.
The first line contains an integer $n$ (2ドル ≤ n ≤ 10^6$), denoting the number of boxes.
The second line contains $n$ integers $a_1, a_2, \dots , a_n$ (1ドル ≤ a_i ≤ 10^7$), where the $i$-th integer $a_i$ denotes the initial number of cookies in the $i$-th box.
Output one line with a single integer denoting the smallest number of cookies that Nicolaus should add to the boxes. If Nicolaus doesn’t have to add any cookies to make the greatest common divisor of the numbers equal to 1ドル,ドル output 0ドル$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 17 | $n = 2$ |
| 2 | 34 | $n ≤ 10$ |
| 3 | 11 | $n ≤ 1000$ |
| 4 | 38 | No additional constraints. |
3 90 84 140
2
Explanation of the example: Indeed, the greatest common divisor (GCD) of 90ドル,ドル 84ドル,ドル and 140ドル$ is 2ドル,ドル so some cookies must be added. If we add only one cookie, we may obtain the quantities 91ドル,ドル 84ドル,ドル 140ドル$ with GCD of 7ドル,ドル or 90ドル,ドル 85ドル,ドル 140ドル$ with GCD of 5ドル,ドル or 90ドル,ドル 84ドル,ドル 141ドル$ with GCD of 3ドル,ドル so this is not enough. After adding two cookies, one to the first box, and one to the second box, we obtain the quantities 91ドル,ドル 85ドル,ドル 140ドル$ with GCD of 1ドル$; hence the answer is 2ドル$. Note that adding both cookies to the first box does not help: we obtain quantities 92ドル,ドル 84ドル,ドル 140ドル$ with GCD of 4ドル$.