/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
A に対して、以下の操作を好きな回数行うことができます。
- 1 以上 N 以下の整数 i を一つ選び、i の正の約数であるようなすべての整数 j について A_j に 1 を足す。
A の要素をすべて等しくすることが可能かを判定し、可能ならばそのために必要な操作回数の最小値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
A の要素をすべて等しくすることが可能ならばそのために必要な操作回数の最小値を、そうでないならば -1 を 1 行で出力せよ。
入力例 1
3 4 7 4
出力例 1
3
1 回目の操作で i=3 を選べば、A=(5,7,5) となります。
2 回目の操作で i=3 を選べば、A=(6,7,6) となります。
3 回目の操作で i=3 を選べば、A=(7,7,7) となります。
3 回未満の操作で A の要素をすべて等しくすることはできないため、答えは 3 です。
入力例 2
5 1 3 4 5 6
出力例 2
5
入力例 3
2 5 2
出力例 3
-1
Score : 500 points
Problem Statement
You are given a length-N integer sequence A=(A_1,A_2,\dots,A_N).
You can perform the following operation on A any number of times.
- Choose an integer i with 1 \leq i \leq N. For every integer j that is a positive divisor of i, add 1 to A_j.
Determine whether it is possible to make all elements of A equal, and if it is possible, find the minimum number of operations required to do so.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
If it is possible to make all elements of A equal, output, in one line, the minimum number of operations required to do so; otherwise, output -1.
Sample Input 1
3 4 7 4
Sample Output 1
3
If you choose i=3 for the first operation, you get A=(5,7,5).
If you choose i=3 for the second operation, you get A=(6,7,6).
If you choose i=3 for the third operation, you get A=(7,7,7).
It is impossible to make all elements of A equal with fewer than three operations, so the answer is 3.
Sample Input 2
5 1 3 4 5 6
Sample Output 2
5
Sample Input 3
2 5 2
Sample Output 3
-1