Trong một buổi học thú vị về số học, bạn được giao một thử thách với dãy số nguyên dương \(A_1, A_2, \dots, A_n\). Nhiệm vụ của bạn như sau:
-
Hãy chọn và loại bỏ một phần tử bất kỳ trong dãy số.
-
Tính \(P\), là tích của tất cả các phần tử còn lại sau khi loại bỏ phần tử đó.
-
Phân tích \(P\) thành thừa số nguyên tố và tính tổng các số mũ trong phân tích đó.
Hãy tìm cách loại bỏ một phần tử sao cho tổng các số mũ trong phân tích thừa số nguyên tố của \(P\) đạt giá trị nhỏ nhất.
Yêu cầu: In ra giá trị nhỏ nhất của tổng số mũ trong phân tích thừa số nguyên tố của \(P\) sau khi loại bỏ một phần tử.
Input
- Dòng đầu chứa một số nguyên \(n\) \((1 \leq n \leq 10^5)\), là số lượng phần tử trong dãy \(A\).
- Dòng thứ hai chứa \(n\) số nguyên dương \(A_i\) \((1 \leq A_i \leq 10^6)\).
Output
- In ra một số nguyên duy nhất là tổng số mũ nhỏ nhất của phân tích thừa số nguyên tố sau khi loại bỏ một phần tử.
Example
Test 1
Input
4
1 2 4 10Output
3Note
Với dãy \(A = \{1, 2, 4, 10\}\):
-
Nếu loại bỏ \(4\), ta có \(P = 1 \cdot 2 \cdot 10 = 20 = 2^2 \cdot 5\), tổng số mũ là \(2 + 1 = 3\).
-
Nếu loại bỏ \(10\), ta có \(P = 1 \cdot 2 \cdot 4 = 8 = 2^3\), tổng số mũ là \(3\).
Kết quả tốt nhất trong trường hợp này là \(3\).
Scoring
- Subtask 1 (\(30\%\) số điểm): \(n \leq 10\), \(A_i \leq 100\).
- Subtask 2 (\(30\%\) số điểm): \(n \leq 10^3\), \(A_i \leq 10^5\).
- Subtask 4 (\(40\%\) số điểm): Không có ràng buộc nào thêm.
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.