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

View as PDF

Submit solution

Points: 1800 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Author:
Problem type

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
2
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ụ.


Comments

There are no comments at the moment.