Editorial for Thay đổi số
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Ở bài này ta sẽ có 1 nhận xét quan trọng là ~gcd(a,b) \le min(a,b)~ với ~a,b\in \mathbb{Z}~. Vì vậy các lượt thay đổi số có thể coi là lượt xóa số đó khỏi hàm tính ~gcd~ để tối ưu hóa đáp án. Từ đó, việc sử dụng cả 2 lượt xóa số sẽ giúp tối ưu đáp án.
Sub 1: ~n = 3~
- Với trường hợp n = 3, để tối ưu đáp án ta sẽ thực hiện lượt xóa 2 số bé nhất và đáp án sẽ là ~max(a_1,a_2,a_3)~.
- ĐPT: ~O(1)~
Sub 2: ~n, a_i \le 1000~
- Với ~a_i \le 1000~ ta thấy rằng đáp án cũng sẽ ~\le 1000~. Vì thế ta sẽ duyệt tất cả các đáp án có thể, đếm xem trong ~n~ số có bao nhiêu số chia hết cho số đang duyệt. Đáp án sẽ là số lớn nhất là ước của ít nhất ~n-2~ số.
- ĐPT: ~O(n * max(a_i))~
Sub 3: ~n, a_i \le 10^5~
- Ta có nhận xét đáp án sẽ là ước của một trong ~n~ số vì thế với từng số ta sẽ duyệt qua các ước của nó bằng cách duyệt đến căn bậc 2 của số đó. Qua mỗi lần duyệt ta lưu số lần 1 số là ước bằng 1 mảng ~cnt~. Đáp án sẽ là số lớn nhất có ~cnt \ge n-2~.
- ĐPT: ~O(n * \sqrt a_i)~
Sub 4: Không có ràng buộc gì thêm
- Nhận xét: một số ~n~ sẽ có số ước xấp xỉ ~\sqrt[3] n~. Thay vì duyệt ước của cả ~n~ số ở trên, ta chỉ cần duyệt các ước của 3 số đầu tiên vì ta chỉ có thể xóa tối đa 2 số nên đáp án chắc chắn là ước của 1 trong 3 số này. Sau đó với từng ước ta tính mảng ~cnt~ của nó bằng cách duyệt ~n~ số. Lưu ý rằng độ lớn của ước có thể vượt qua giợi hạn chứa của mảng nên ta cần dùng đến ~map~. Đáp án vẫn se là số lớn nhất có ~cnt \ge 2~.
- ĐPT: ~O(n * 3*\sqrt[3]a_i+3*\sqrt a_i)~