Kiến thức cần biết trước: Backtrack, Quy hoạch động, Sàng nguyên tố.

Subtask ~1~: ~N \le 20~.

Sinh nhị phân, thử toàn bộ các cách chọn.

Độ phức tạp: ~O~ (~2^N \times N \times log (a_i)~).

Subtask ~2~: ~N \le 1000~.

Quy hoạch động: Gọi ~dp_i~ là tổng điểm tối đa khi ta xét hết vì sao thứ ~i~ và vì sao cuối cùng là vì sao thứ ~i~.

Ban đầu, ~dp_1 = 1~.

Ta có ~dp_i~ ~=~ ~max~ ~(dp_j~ ~+~ ~gcd (a_i, a_j)~ ~)~ với ~1 \le j < i~.

Độ phức tạp: ~O~ (~N^2 \times log (a_i)~).

Subtask ~5~: Không có ràng buộc gì thêm.

Vì subtask ~3~ và ~4~ thuật toán không quá rõ ràng, nên mình sẽ chuyển đến subtask ~5~ luôn.

Trong công thức quy hoạch động ở subtask ~2~, ta có thể cố định ~gcd (a_i, a_j)~.

Nhận xét: ~gcd (a_i, a_j)~ phải là ước của ~a_i~. Đồng thời, một số ~\le 2 \times 10^5~ có tối đa khoảng ~100~ ước.

Ta tiền xử lý trước vector ~vec_i~ là vector chứa mọi ước của số ~i~. Điều này có thể thực hiện bằng sàng ước.

Gọi ~f_y~ là ~max~ của các giá trị ~dp_x~ sao cho ~a_x~ chia hết cho ~y~. Giá trị ~f_y~ sẽ được cập nhật liên tục đồng thời với giá trị ~dp_i~.

Có ~dp_1 = 1~ như subtask ~2~. Lưu ý, ta cũng cần gán trước ~f_y = dp_1~ nếu ~y~ là ước của ~a_1~, và ~f_y = -inf~ nếu ~y~ không là ước của ~a_1~.

Lúc này, ta duyệt ~x~ là ước của ~a_i~. Ta có công thức quy hoạch động mới:

$$dp_i = max (f_x + x)$$

Lưu ý, có thể ~x~ ở đây không phải ước chung lớn nhất. Nhưng điều đó không quan trọng, vì nếu ~x~ không là ước chung lớn nhất, sẽ có một giá trị ~x~ khác tối ưu hơn, và ~dp_i~ sẽ được cập nhật từ giá trị ~x~ đó.

Sau khi cập nhật ~dp_i~, ta cập nhật ~f_y~ ~=~ ~max~ (~f_y, dp_i~) với ~y~ là ước của ~a_i~.

Độ phức tạp: ~O~ (~N \times log (N)~ ~+~ ~N \times 100~).