Elearning CodePath – CTP Online Judge

Độ dài nhỏ nhất của dãy số

GRAPH003

🟢 Medium #Graph #Math #BFS/DFS #DSU #Interval

### 📝 Bài toán
Cho dãy số nguyên gồm n phần tử a1, a2, ..., an. Bạn thực hiện liên tiếp các phép biến đổi sau:
- Chọn 2 giá trị a, b sao cho a, b không nguyên tố cùng nhau (hay ước chung lớn nhất của a và b lớn hơn 1).
- Xóa 2 giá trị a, b ra khỏi dãy đã cho và thêm vào giá trị a * b.

Yêu cầu: Hãy tính độ dài nhỏ nhất của dãy số sau khi thực hiện liên tiếp các phép biến đổi trên.

### 📥 Định dạng Đầu vào
- Dòng đầu tiên chứa số nguyên dương n (n <= 100).
- Dòng tiếp theo chứa n số nguyên dương a1, a2, ..., an.

### 📤 Định dạng Đầu ra
- Một số nguyên duy nhất là độ dài nhỏ nhất của dãy số.

### ✨ Ví dụ
| Input | Output | Giải thích |
| :--- | :--- | :--- |
| 6<br>3 2 3 1 7 1 | 5 | Chọn hai số 3 và 3 (GCD=3 > 1). Xóa chúng và thêm 3 * 3 = 9. Dãy còn [9, 2, 1, 7, 1]. Không còn cặp nào có GCD > 1. |
| 5<br>7 6 2 49 3 | 2 | - Chọn 7 và 49 -> 343. Dãy: [6, 2, 3, 343].<br>- Chọn 6 và 2 -> 12. Dãy: [12, 3, 343].<br>- Chọn 12 và 3 -> 36. Dãy: [36, 343]. |

### 🏷 Subtasks
- Subtask 1 (50% số điểm): n <= 100, ai <= 10^4.
- Subtask 2 (50% số điểm): n <= 100, ai <= 10^7.

✅ Đã AC: 0 / 0 submissions