Subtask 2

Vì ~a_i = a_j~ nên trọng số các cạnh ban đầu bằng ~2~ do đó ta chỉ cần quan tâm các cạnh thêm vào có trọng số bằng ~1~ là được.

Subtask 3,4

Ta xây đồ thị ~2~ phía. Bên trái là ~n~ đỉnh đã cho. Bên phải là ~10^5~ đỉnh giả. Thêm cạnh nối giữa đỉnh ~u~ bên trái và đỉnh ~v~ bên phải với trọng số ~\frac{a_u}{v}~ nếu ~a_u~ chia hết cho ~v~.

Nhận xét: Đường đi ngắn nhất của đồ thị gốc bằng đường đi ngắn nhất của đồ thị mới

Chứng minh:

Đặt ~d~ là ~1~ ước chung của ~a_u~ và ~a_v~. Kí hiệu ~(u, v, w)~ là một cạnh nối giữa đỉnh ~u~ bên trái và đỉnh ~v~ bên phải với trọng số ~w~.

Trong đồ thị ~2~ phía, cạnh ~(u, d, \frac{a_u}{d})~ và ~(v, d, \frac{a_v}{d})~ đều tồn tại, do đó tồn tại đường đi từ ~u~ tới ~v~ có tổng trọng số là ~(a_u + a_v) / d~ với ~d~ là ~1~ ước chung bất kì. Trong tất cả các giá trị có thể của ~d~, dễ dàng thấy rằng ~d = gcd(a_u, a_v)~ là tạo ra trọng số nhỏ nhất.

Do đó, ~1~ cách đi từ ~u~ tới ~v~ mà chỉ sử dụng các đỉnh giả trung gian trong đồ thị mới có trọng số không nhỏ hơn ~(a_u + a_v) / gcd(a_u, a_v)~. Vì vậy nếu trong đường đi ngắn nhất của đồ thị mới có đoạn đi từ ~u~ tới ~v~ chỉ qua các đỉnh giả trung gian thì chắc chắn tổng trọng số của quãng này là ~(a_u + a_v) / gcd(a_u, a_v)~, hay chính là tương ứng với việc đi trực tiếp từ đỉnh ~u~ tới đỉnh ~v~ trong đồ thị gốc. -> dpcm

Mỗi đỉnh ~u~ bên trái có [số ước của ~a_u~] cạnh nối sang phải. Các đỉnh có cùng trọng số thì chập vào làm một (do độ dài đường đi ngắn nhất là bằng nhau). Đặt ~A = max (a_i)~. Khi đó tổng số cạnh nối là: số ước của ~1~ + số ước của ~2~ + … + số ước của ~A~ = ~A \times log(A)~.

Subtask 5

Ở subtask trước, ta chập các đỉnh chung trọng số vào làm ~1~ để thu được đồ thị có ~A \times log(A)~ cạnh.

Ở subtask này, ta chỉ chập các đỉnh có chung trọng số nếu như chúng không phải đầu mút của cạnh nào trong ~m~ cạnh được thêm vào.

Nếu như có đỉnh ~u~ là đầu mút của ~1~ cạnh nào đó trong ~m~ cạnh thêm vào, đồng thời cũng có ~1~ đỉnh bất kì nào đó có cùng trọng số với ~u~, ta sẽ xây thêm [số ước của ~a_u~] cạnh nữa nối từ đỉnh ~u~ (bên trái) tới các đỉnh ước của nó ở bên phải và xây các cạnh nhận ~u~ làm đầu mút trong ~m~ cạnh được thêm với cách đỉnh tương ứng bên trái (như vậy đồ thị không còn là đồ thị ~2~ phía nữa nhưng vẫn bảo đảm được tính chất của đường đi ngắn nhất)

Khi đó, số cạnh được thêm vào là ~m \times~ [số ước của ~A~] ~+ m~. Do ~a_i \le 10^5~ nên nó có tối đa ~65~ ước nên số cạnh thêm vào là ~66 \times m~.

Vậy tổng số cạnh bây giờ là ~A \times log(A) + 66 \times m~.

Độ phức tạp của Dijkstra là: ~O((A \times log(A) + 66m) \times log (n))~