TLEOJ Contest #16 - Chi phí băng số

Điểm: 1800 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 512M

Input: bàn phím

Output: màn hình

Tác giả:

icebearlovecode

Dạng bài

Tại bảng số ở nhà Hiếu có $n$ ô vuông, ô thứ $i$ có giá trị là $a_i$ . Hiếu và Đại sẽ chơi một trò chơi như sau:

Đại bắt đầu từ ô thứ nhất, di chuyển đến ô bất kì có giá trị không là số nguyên tố cùng nhau với giá trị ô hiện tại.
Nếu như tồn tại một ô không thể đi đến theo bất cứ cách nào, Đại sẽ chiến thắng.
mỗi ô có thể đi đến nhiều lần.

Để Đại không thể chiến thắng dễ dàng như vậy, Hiếu quyết định sẽ sửa giá trị tại một số ô. Nếu Hiếu sửa giá trị thứ $i$ cách chọn một số nguyên dương $k$ bất kì và nhân nó với $a_i$ chi phí cho việc sửa giá trị sẽ là $k$ (nói cách khác $a_i=a_i \cdot k$ ).

Yêu cầu: Tìm tổng chi phí nhỏ nhất để Đại không thể thắng.

Input and Output

Input

Dòng đầu tiên chứa một số nguyên dương $n$ ( $n\le 10^5$ ).
Dòng thứ hai chứa $n$ số nguyên dương $a_i$ , $i=1,2,3\dots n$ ( $a_i\le 10^5$ )

Output

Gồm một dòng duy nhất chứa tổng chi phí nhỏ nhất.

Subtask

Subtask $1$ ( $20\%$ ) : Với mọi $1\le i < j \le n$ thì $\text{gcd}(a_i,a_j)=1$ .
Subtask $2$ ( $20\%$ ) : $n\le 10,a_i\le 10$ .
Subtask $3$ ( $20\%$ ) : $a_i\le 2$ .
Subtask $4$ ( $40\%$ ) : không có giới hạn gì thêm

Test

Input

4
4 10 5 3

Output

Note

Nhân $a_4$ với $2$ ta được dãy $a=\{4;10;5;6\}$ Đại sẽ đi theo các ô như sau:
$1\rightarrow 4\rightarrow 2 \rightarrow 3$ .
dưới đây là hình minh họa cho test ví dụ.

Bình luận

Không có bình luận nào.