Ở 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)~