Trước hết ta có nhận xét là một số $a_i$ sẽ chỉ tăng tối đa đến $2\times \max a_i$ vì nếu quá giá trị này thì giảm về $1$ sẽ tối ưu hơn.
Đặt $S = 2 \times 10^7$, đầu tiên ta sử dụng sàng nguyên tố (hoặc mảng hằng T_T) để liệt kê các số nguyên tố không vượt quá $S$. Ta sẽ cố định $p$ và tính toán chi phí nhỏ nhất, xét hai trường hợp như sau:
- Nếu $p \leq \sqrt{S}$, ta sẽ tăng/giảm các số $a_i$ thành một lũy thừa của $p$. Hiển nhiên để cực tiểu hóa chi phí ta sẽ chọn giá trị gần với $a_i$ nhất. Vì hàm mũ tăng rất nhanh nên công đoạn này có thể "duyệt trâu" với độ phức tạp gần $\mathcal{O}(n)$.
- Nếu $p > \sqrt{S}$, theo nhận xét ở trên việc tăng $a_i$ vượt quá $S$ là vô nghĩa nên ta sẽ chỉ tăng/giảm các giá trị $a_i$ cho bằng $p$. Nói cách khác ta cần tính tổng các $|a_i - p|$, đây là một bài toán cơ bản có thể giải trong $O(\log n)$ bằng chặt nhị phân và mảng cộng dồn.
**Bonus.** Ngoài ra bài toán có một lời giải khác sử dụng thuật toán ngẫu nhiên có thể tham khảo tại [đây](https://codeforces.com/blog/entry/74459) (bài F).
chithanhnguyen
Created at
0 likes