Tổng số mũ
Cho dãy số nguyên dương \(A_1, A_2, \dots, A_n\). Hãy chọn và loại bỏ một phần tử bất kỳ khỏi dãy số, sau đó tính \(P\) là tích của tất cả các phần tử còn lại.
Phân tích \(P\) thành thừa số nguyên tố:
\(P = p_1^{e_1} \times p_2^{e_2} \times \dots \times p_k^{e_k}\)
Tính tổng các số mũ: \(S = e_1 + e_2 + \dots + e_k\).
Hãy tìm cách loại bỏ một phần tử sao cho tổng \(S\) đạt giá trị nhỏ nhất.
Dữ liệu vào
- Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 10^5\)).
- Dòng thứ hai chứa \(n\) số nguyên dương \(A_i\) (\(1 \le A_i \le 10^6\)).
Dữ liệu ra
- In ra giá trị nhỏ nhất của tổng các số mũ \(S\).
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 | 3 | Dãy: 1, 2, 4, 10. |
| 1 2 4 10 | Loại bỏ 10: tích còn lại = 1x2x4 = 8 = 2^3, tổng mũ = 3. | |
| Loại bỏ 4: tích = 1x2x10 = 20 = 2^2 x 5^1, tổng mũ = 3. | ||
| Kết quả nhỏ nhất là 3. |
Subtasks
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | 30% | \(n \le 10, A_i \le 100\) |
| 2 | 30% | \(n \le 10^3, A_i \le 10^5\) |
| 3 | 40% | Không ràng buộc thêm |
Gợi ý
Gọi \(E(x)\) là tổng số mũ khi phân tích \(x\) ra thừa số nguyên tố. Tổng số mũ của tích tất cả các phần tử trong dãy là \(E(A_1) + E(A_2) + \dots + E(A_n)\).
Khi loại bỏ \(A_k\), tổng số mũ giảm đi đúng \(E(A_k)\). Do đó, cần tìm phần tử có \(E(A_k)\) lớn nhất để loại bỏ.
Kết quả = \(\sum_{i=1}^{n} E(A_i) - \max_{i=1}^{n} E(A_i)\).
Comments