PreVOI 2025 - Contest 2 - Đồ thị bội chung nhỏ nhất
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Phong là một người yêu thích các bài toán liên quan đến đồ thị và số học. Một ngày nọ, anh phát hiện ra một bài toán thú vị trong khi làm việc với một mảng số nguyên và một đồ thị đặc biệt.
Từ một mảng ~a_1, a_2, \dots, a_n~, Phong xây dựng ra đồ thị vô hướng đầy đủ ~G~ với ~n~ đỉnh được đánh số từ ~1~ đến ~n~, trong đó giữa hai đỉnh ~i~ và ~j~ ~(i < j)~ có một cạnh vô hướng kết nối chúng với trọng số là ~\operatorname{LCM}(A_i, A_{i+1}, \dots, A_j)~.
Nhắc lại, ~\operatorname{LCM}(A_i, A_{i+1}, \dots, A_j)~ là số nguyên dương nhỏ nhất chia hết cho ~A_i, A_{i+1}, \dots, A_j~. Ví dụ ~\operatorname{LCM}(4, 6) = 12~ hay ~\operatorname{LCM}(3, 7, 14) = 42~.
Phong đánh dấu ~k~ đỉnh khác nhau ~p_1, p_2, \dots, p_k~ trên đồ thị ~G~ làm các đỉnh đặc biệt. Anh muốn chọn một số cạnh trong ~G~ sao cho mỗi cặp đỉnh đặc biệt đều được kết nối với nhau. Hai đỉnh ~u~ và ~v~ được xem là kết nối với nhau nếu tồn tại một đường đi ~(u = x_0, x_1, x_2, \dots, x_d = v)~ giữa hai đỉnh đó, sao cho với mỗi cặp đỉnh liên tiếp ~(x_{i-1}, x_i)~ ~(1 \le i \le d)~ được kết nối trực tiếp với nhau bằng một cạnh đã chọn.
Vì có nhiều cách chọn, Phong muốn tổng trọng số của các cạnh đã chọn là nhỏ nhất.
Yêu cầu: Bạn hãy giúp Phong tìm ra tổng trọng số nhỏ nhất đó!
Input
Dòng đầu tiên chứa hai số nguyên dương ~n, k~ ~(1 \le k \le n \le 3 \cdot 10^5)~ lần lượt là số đỉnh của đồ thị ~G~ và số đỉnh đặc biệt.
Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 3 \cdot 10^5)~ mô tả mảng ~a~.
Dòng cuối cùng chứa ~k~ số nguyên dương phân biệt ~p_1, p_2, \dots, p_k~ ~(1 \le p_i \le n)~ mô tả dãy ~p~ — các đỉnh đặc biệt được chọn.
Output
Dòng đầu tiên chứa một số nguyên duy nhất ~t~ ~(0 \le t \le 10^{18})~ là tổng trọng số nhỏ nhất trong phương án tối ưu.
Dòng thứ hai chứa một số nguyên ~m~ ~(0 \le m \le 10^6)~ mô tả số cạnh được chọn trong phương án tối ưu.
~m~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~u, v~ ~(1 \le u, v \le n, u \ne v)~ mô tả một cạnh được chọn. Các cạnh này có thể xuất hiện theo bất kỳ thứ tự nào, và mỗi cạnh chỉ xuất hiện tối đa một lần.
Nếu có nhiều hơn một phương án tối ưu, in ra bất kỳ. Có thể chứng minh được rằng luôn tồn tại phương án tối ưu thỏa mãn các điều kiện ở trên.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~30\%~ | ~n \le 6~. |
| 2 | ~20\%~ | ~n \le 200~. |
| 3 | ~20\%~ | ~n \le 2000~. |
| 4 | ~15\%~ | ~a_i \le 16~ với mọi ~1 \le i \le n~. |
| 5 | ~15\%~ | Không có giới hạn gì thêm |
Ngoài ra, với mỗi test, bạn nhận được ~60\%~ số điểm của test đó nếu bạn cho biết chính xác tổng trọng số tối thiểu mà không cho biết phương án chọn cạnh để đạt được tổng trọng số đó, hoặc nếu phương án bạn đưa ra không hợp lệ, không khớp với tổng trọng số đã tính toán, hoặc không thỏa mãn điều kiện,...
Sample Input 1
3 2
1 2 3
1 3
Sample Output 1
6
1
3 1
Sample Input 2
8 4
6 3 2 3 1 10 3 15
6 8 2 7
Sample Output 2
61
4
2 5
7 8
5 6
5 8
Notes
Ở ví dụ thứ nhất, ta có dãy ~a = (1, 2, 3)~, do đó đồ thị ~G~ có ~3~ đỉnh với các cạnh có trọng số lần lượt là:
Cạnh ~(1, 2)~ có trọng số ~\operatorname{LCM}(a_1, a_2) = \operatorname{LCM}(1, 2) = 2~.
Cạnh ~(2, 3)~ có trọng số ~\operatorname{LCM}(a_2, a_3) = \operatorname{LCM}(2, 3) = 6~.
Cạnh ~(1, 3)~ có trọng số ~\operatorname{LCM}(a_1, a_2, a_3) = \operatorname{LCM}(1, 2, 3) = 6~.
Với các đỉnh đặc biệt là ~1~ và ~3~, để kết nối chúng với trọng số nhỏ nhất, ta chọn cạnh ~(1, 3)~ với tổng trọng số là ~6~. Đây là cách có tổng trọng số nhỏ nhất. Bạn có thể tham khảo hình bên dưới, trong đó các cạnh nét liền biểu thị các cạnh được chọn trong phương án tối ưu, các cạnh nét đứt biểu thị cạnh không được chọn.

Minh họa cho ví dụ thứ nhất

Minh họa cho ví dụ thứ hai
Bình luận