Elearning CodePath – CTP Online Judge

Chọn Quà

CHOOSGIF

🟢 Easy #Math #Combinatorics #Optimization

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho $N$ hộp quà, hộp quà thứ $i$ có giá trị $A_i$ ($A_i$ đôi một khác nhau).
Jame được chọn 3 hộp quà (giả sử là $A_x, A_y, A_z$).
Tổng giá trị nhận được ($V$) được tính bằng:
$V = (A_x + A_y + A_z) + \text{Thưởng}$
Trong đó, giá trị phần thưởng được xác định là:
* $\text{Thưởng} = P$, với $P$ là ước chung nguyên tố lớn nhất của ba số $A_x, A_y, A_z$.
* Nếu ba số $A_x, A_y, A_z$ không có ước chung nguyên tố nào (tức là $\gcd(A_x, A_y, A_z)$ không có ước nguyên tố, hoặc $\gcd(A_x, A_y, A_z) = 1$), thì $\text{Thưởng} = 0$.

Yêu cầu: Hãy tính tổng giá trị lớn nhất ($V_{\text{max}}$) mà Jame có thể nhận được.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `CHOOSGIF.INP`:

* Dòng 1: Ghi số nguyên dương $N$.
* Dòng 2: Ghi $N$ số nguyên dương $A_1, A_2, \dots, A_N$.

Giới hạn: (Không được cung cấp trong đề gốc, ta giả sử giới hạn thường gặp cho bài toán tổ hợp/số học là)
* $3 \le N \le 10^3$.
* $1 \le A_i \le 10^5$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `CHOOSGIF.OUT` kết quả tìm được (tổng giá trị lớn nhất).

---
### ✨ Ví dụ

| Input (`CHOOSGIF.INP`) | Output (`CHOOSGIF.OUT`) |
| :--- | :--- |
| `4` <br> `9 11 12 15` | `39` |

Giải thích: $A = \{9, 11, 12, 15\}$.
1. $\{9, 12, 15\}$: Tổng $9+12+15 = 36$. $\gcd(9, 12, 15) = 3$. $3$ là số nguyên tố. Ước chung nguyên tố lớn nhất là $3$.
   Giá trị $= 36 + 3 = 39$.
2. $\{9, 11, 12\}$: $\gcd = 1$. Thưởng $0$. Giá trị $32 + 0 = 32$.
3. $\{9, 11, 15\}$: $\gcd = 1$. Thưởng $0$. Giá trị $35 + 0 = 35$.
4. $\{11, 12, 15\}$: $\gcd = 1$. Thưởng $0$. Giá trị $38 + 0 = 38$.
Giá trị lớn nhất là $39$.

---
### 🏷 Subtasks

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | $N \le 50$; $A_i \le 100$ | $30\%$ |
| 2 | $N \le 100$; $A_i \le 10^4$ | $30\%$ |
| 3 | $N \le 10^3$; $A_i \le 10^5$ | $40\%$ |

---

✅ Đã AC: 0 / 0 submissions