Tích ước chung lớn nhất trên cây (Tin học trẻ toàn quốc 2025 – Vòng loại đợt 3 – Bảng C1, C2)

Nguồn: Tin học trẻ toàn quốc 2025 Độ khó: Khó Cây, LCA Số học

Đề bài

Cho một cây gồm $N$ đỉnh đánh số từ 1 đến $N$; trên đỉnh thứ $i$ có ghi số nguyên dương $A_i$.

Có $Q$ truy vấn, truy vấn thứ $k$ cho bởi ba số $u_k, v_k, x_k$. Hãy tính

$$S_k = \Big( \prod_{t} \gcd(A_t, x_k) \Big) \bmod (10^9 + 7),$$

trong đó tích lấy trên mọi đỉnh $t$ nằm trên đường đi đơn từ $u_k$ đến $v_k$ (kể cả hai đầu mút), $\gcd$ là ước chung lớn nhất.

Dữ liệu vào:

• Dòng đầu: hai số nguyên dương $N, Q$ ($N, Q \le 10^5$).
• Dòng thứ hai: $N$ số nguyên dương $A_1, A_2, \ldots, A_N$ ($A_i \le 10^7$).
• $N - 1$ dòng tiếp theo, mỗi dòng hai số $u, v$ – một cạnh của cây.
• $Q$ dòng cuối, dòng thứ $k$ chứa $u_k, v_k, x_k$ ($1 \le u_k, v_k \le N$; $x_k \le 10^7$).

Kết quả: $Q$ dòng, dòng thứ $k$ ghi $S_k$.

Subtask:

• Subtask 1 (30% số điểm): $N, Q \le 1000$.
• Subtask 2 (30% số điểm): mọi $x_k$ đều là lũy thừa của 2 (số mũ nguyên không âm).
• Subtask 3 (40% số điểm): không có ràng buộc gì thêm.

Giới hạn thời gian: 1 giây. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ – input

4 3
1 2 3 4
1 2
2 3
3 4
1 4 1
4 4 2
1 4 2

Ví dụ – output

1
2
4

Giải thích: cây là đường thẳng $1 - 2 - 3 - 4$.

• Truy vấn 1: $x = 1$ nên mọi $\gcd$ đều bằng 1, $S_1 = 1$.
• Truy vấn 2: đường đi chỉ gồm đỉnh 4, $S_2 = \gcd(4, 2) = 2$.
• Truy vấn 3: đường đi $1 \to 2 \to 3 \to 4$, $S_3 = \gcd(1,2) \cdot \gcd(2,2) \cdot \gcd(3,2) \cdot \gcd(4,2)$ $= 1 \cdot 2 \cdot 1 \cdot 2$ $= 4$.

Nguồn: Hội thi Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 3 – Bảng C1, C2 (bài TREEGCD). Đề được mình viết lại cho dễ đọc; phần giải thích ví dụ là mình tự thêm.

Lời mở đầu

Đây là bài khó nhất của đợt 3, kết hợp hai mảng kiến thức: số học (phân tích thừa số nguyên tố, sàng) và cây (LCA, DFS). Cái khó là $\gcd$ không "cộng dồn" được như tổng – không thể làm tiền tố trực tiếp. Mẹo là tách $\gcd$ thành từng lũy thừa nguyên tố, khi đó mỗi phần trở thành bài đếm số đỉnh trên đường đi – thứ mà LCA làm rất giỏi. Subtask 2 ($x = 2^e$) chính là bước đệm để nghĩ ra mẹo này.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởnglũy thừa nguyên tốCách 1đi từng bướcCách 2x = 2^eCách 3DFS offlineTổng kếtkết quả

Bộ testBộ test có gì?

Bộ test của mình gồm 20 test chia đúng tỉ lệ subtask: test 1–6 (subtask 1), 7–12 (subtask 2), 13–20 (subtask 3). Test 1 là ví dụ của đề. Lời giải chính thức của mình (cùng ý tưởng cách 3, cài đặt tối ưu hơn với LCA Tarjan) đã được nộp thử trên hệ thống chấm chính thức tinhoctre.vn và đạt 100/100 điểm.

Test	$N$	$Q$	Độ sâu cây (gốc 1)	Dạng cây	$A$ lớn nhất	$x$ lớn nhất	$x$ đều là $2^e$?
1	4	3	3	nhỏ	4	2	có
2	1	5	0	nhỏ	21	8.168.160	không
3	1.000	1.000	17	ngẫu nhiên / nhị phân	9.997.020	9.979.200	không
4	1.000	1.000	691	đường thẳng	9.996.000	9.975.040	không
5	1.000	1.000	2	hình sao	9.992.061	9.990.441	không
6	1.000	1.000	674	đường thẳng	8.388.608	8.388.608	có
7	100.000	100.000	34	ngẫu nhiên / nhị phân	9.437.184	8.388.608	có
8	100.000	100.000	61.484	đường thẳng	9.437.184	8.388.608	có
9	100.000	100.000	40.346	chổi / sâu	8.388.608	8.388.608	có
10	100.000	100.000	73.291	đường thẳng	8.388.608	8.388.608	có
11	100.000	100.000	28	ngẫu nhiên / nhị phân	9.999.763	8.388.608	có
12	100.000	100.000	39.739	chổi / sâu	9.999.860	8.388.608	có
13	100.000	100.000	42	ngẫu nhiên / nhị phân	9.999.910	9.999.987	không
14	100.000	100.000	32	ngẫu nhiên / nhị phân	9.998.100	9.998.560	không
15	100.000	100.000	78.788	đường thẳng	9.998.560	9.998.560	không
16	100.000	100.000	49.996	chổi / sâu	9.999.985	9.999.784	không
17	100.000	100.000	58.142	đường thẳng	9.699.690	9.699.690	không
18	100.000	100.000	2	hình sao	9.998.560	9.999.603	không
19	100.000	100.000	39.286	chổi / sâu	9.999.933	9.998.100	không
20	100.000	100.000	32	ngẫu nhiên / nhị phân	9.998.100	9.998.100	không

• Cây có đủ dạng: đường thẳng dài (độ sâu tới hàng chục nghìn – "sát thủ" của cách đi từng bước), hình sao, chổi, cây ngẫu nhiên nông.
• Test 10 và 17 dùng $A$, $x$ cố định có số mũ lớn ($2^{23}$; $2 \cdot 3 \cdot 5 \cdots 19$) trên đường thẳng dài.

Kết quả chạy thật của các cách theo từng subtask:

Subtask	Điều kiện	Test	Cách 1 C++	Cách 1 Python	Cách 2 C++	Cách 2 Python	Cách 3 C++
Subtask 1 (30%)	$N, Q \le 1000$	1–6	6/6	6/6	2/6	2/6	6/6
Subtask 2 (30%)	mọi $x_k$ là lũy thừa của 2	7–12	2/6	0/6	6/6	0/6	6/6
Subtask 3 (40%)	không ràng buộc thêm	13–20	4/8	1/8	0/8	0/8	8/8

Ý tưởngTách gcd thành các lũy thừa nguyên tố

Nhận xét 1. Nếu $x = \prod p^{e_p}$ thì $\gcd(A, x)$ $= \prod p^{\min(e_p(A),\, e_p)}$, với $e_p(A)$ là số mũ của $p$ trong $A$. Nhân trên cả đường đi:

$$S = \prod_{p \mid x} p^{\,\sum_t \min(e_p(A_t),\, e_p)}.$$

Nhận xét 2 – mẹo đếm. $\min(e_p(A), e)$ bằng số các $k \in [1, e]$ mà $p^k \mid A$. Ví dụ $A = 12 = 2^2 \cdot 3$, $e = 3$: $2^1 \mid 12$, $2^2 \mid 12$, $2^3 \nmid 12$ → đếm được 2 = $\min(2, 3)$. Đổi thứ tự tổng:

Công thức

Số mũ của $p$ trong $S$ $= \displaystyle\sum_{k=1}^{e_p} \text{cnt}_{p^k}(u, v)$, với $\text{cnt}_{q}(u, v)$ = số đỉnh trên đường đi $u$–$v$ có $A_t$ chia hết cho $q$.

Nhận xét 3 – đếm trên đường đi. Gọi $f_q(w)$ là số đỉnh trên đường từ gốc tới $w$ có $q \mid A$. Với $l = \text{LCA}(u, v)$ và $\text{par}(l)$ là cha của $l$:

$$\text{cnt}_q(u, v) = f_q(u) + f_q(v) - f_q(l) - f_q(\text{par}(l)).$$

Vì $x \le 10^7$ nên $x$ có không quá 8 ước nguyên tố khác nhau và tổng các số mũ không quá 23 – mỗi truy vấn chỉ cần vài chục giá trị $q = p^k$.

Em sửa cây (danh sách $A$ và cha của các đỉnh 2..n), truy vấn rồi bấm Tiếp để xem cách đếm:

A1..An = cha của 2..n = u v x =

Ví dụ nhanh:

Cách 1Đi trên đường đi, nhân trực tiếp (subtask 1)

BFS từ gốc 1 để có cha và độ sâu. Với mỗi truy vấn, đỉnh nào sâu hơn thì nhảy lên cha, nhân $\gcd$ của đỉnh đó vào kết quả – tới khi hai đỉnh gặp nhau ở LCA thì nhân nốt đỉnh LCA.

C++▶ Chạy tay từng dòng codeCách 1: đỉnh sâu hơn nhảy lên cha, nhân gcd từng đỉnh trên đường đi.

Dữ liệu vào (stdin) – sửa thoải mái4 3 1 2 3 4 1 2 2 3 3 4 1 4 1 4 4 2 1 4 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(N)$

Thời gian$O(Q \cdot N \log A)$ trường hợp xấu

Kết quả chạy thật: Bản C++ đúng 12/20 test, quá thời gian test 8–10, 12, 15–17, 19, chạy lâu nhất 4.006s. Bản Python đúng 7/20 test, quá thời gian test 7–17, 19–20, chạy lâu nhất 3.943s. Cách này đúng với mọi test nhưng mỗi truy vấn tốn $O(\text{độ dài đường đi})$: trên cây nông (sao, ngẫu nhiên) vẫn chạy kịp cả với $N = Q = 10^5$, còn trên cây dạng đường thẳng thì tới $10^5 \cdot 10^5$ phép – quá thời gian.

Cách 2Khi x là lũy thừa của 2: đếm tiền tố trên cây (subtask 2)

Chỉ có một số nguyên tố $p = 2$. Đặt $v_2(A)$ là số mũ của 2 trong $A$ ($\le 23$ vì $A \le 10^7 < 2^{24}$). Theo nhận xét 2, số mũ của 2 trong đáp án là $\sum_{k=1}^{e} \text{cnt}_k(u, v)$ với $\text{cnt}_k$ = số đỉnh trên đường đi có $v_2(A_t) \ge k$.

Ta tính sẵn pre[w][k] = số đỉnh trên đường gốc → $w$ có $v_2 \ge k$ (24 giá trị cho mỗi đỉnh, tính khi BFS: pre[w][k] = pre[cha][k] + (v2[w] >= k)), và tìm LCA bằng nhảy nhị phân (binary lifting). Mỗi truy vấn chỉ còn $O(\log N + 23)$.

C++▶ Chạy tay từng dòng codeCách 2 (x = 2^e): pre[w][k] đếm số đỉnh có v2 ≥ k trên đường gốc → w, ghép bằng LCA.

Dữ liệu vào (stdin) – sửa thoải mái4 3 1 2 3 4 1 2 2 3 3 4 1 4 1 4 4 2 1 4 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Bảng nhảy nhị phân up[][] và hàm lca được tính gọn trong một bước để khung chạy tay không quá dài.

1. up[w][j] là tổ tiên thứ $2^j$ của $w$; tính ngay khi BFS gặp $w$ vì cha của $w$ đã có đủ bảng.
2. pre[0] toàn 0 đóng vai trò "cha của gốc", nên khi LCA là gốc thì pl = 0 vẫn đúng.
3. Kết quả là $2^E$ với $E$ có thể tới $23 \cdot 10^5$ – dùng lũy thừa nhanh power theo modulo.

Không gian$O(N (\log N + 24))$

Thời gian$O((N + Q)(\log N + 24))$

Kết quả chạy thật: Bản C++ đúng 8/20 test, sai test 2–5, 13–20, chạy lâu nhất 0.348s. Bản Python (chậm vì vòng lặp Python, chỉ qua test nhỏ) đúng 2/20 test, sai test 2–5, quá thời gian test 7–20, chạy lâu nhất 2.997s. Cách 2 chỉ đúng khi $x$ là lũy thừa của 2 nên ăn trọn subtask 2 (và các test của subtask 1 mà $x$ là lũy thừa của 2). Nếu ghép thêm cách 1 cho $N, Q \le 1000$ thì được 60 điểm.

Cách 3Mọi lũy thừa nguyên tố + DFS offline (full điểm)

Tổng quát hoá cách 2 cho mọi $p$: cần $f_q(w)$ với mọi lũy thừa nguyên tố $q = p^k \le 10^7$ – không thể lưu bảng cho từng đỉnh. Ta làm offline:

1. Sàng ước nguyên tố nhỏ nhất tới $10^7$ để phân tích nhanh $A_i$ và $x_k$.
2. Với mỗi truy vấn, tìm $l = \text{LCA}(u, v)$ và gắn truy vấn vào 4 đỉnh: $u$ (dấu +), $v$ (+), $l$ (−), $\text{par}(l)$ (−).
3. DFS từ gốc, duy trì mảng cnt[q]: vào đỉnh $w$ thì cnt[q]++ với mọi lũy thừa nguyên tố $q \mid A_w$, ra khỏi $w$ thì cnt[q]--. Như vậy khi đang đứng ở $w$, cnt[q] đúng bằng $f_q(w)$.
4. Đứng ở đỉnh $w$, với mỗi truy vấn gắn vào $w$ (dấu $s$), cộng $s \cdot \text{cnt}[p^j]$ ($j = 1..e_p$) vào số mũ của $p$ trong đáp án truy vấn đó.
5. Cuối cùng $S_k = \prod p^{\text{số mũ}} \bmod (10^9+7)$ bằng lũy thừa nhanh.

C++▶ Chạy tay từng dòng codeCách 3: gắn truy vấn vào u, v, lca, cha(lca); DFS duy trì cnt[p^k] trên đường gốc → đỉnh.

Dữ liệu vào (stdin) – sửa thoải mái4 3 1 2 3 4 1 2 2 3 3 4 1 4 1 4 4 2 1 4 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Bỏ qua phần sàng 10^7 và các bước bên trong hàm lca/primePowers để khung gọn. Nhãn dưới đỉnh: "+q0" nghĩa là truy vấn 0 gắn vào đỉnh này với dấu +.

1. DFS viết không đệ quy (dùng mảng it[u] là vị trí kề tiếp theo cần thăm) vì cây đường thẳng sâu tới $10^5$, đệ quy dễ tràn ngăn xếp.
2. Các cặp $(p, e)$ của mọi truy vấn lưu liên tiếp trong hai mảng P, E (truy vấn $k$ chiếm đoạn st[k]..st[k+1]-1) thay vì vector lồng nhau – đỡ cấp phát bộ nhớ, chạy nhanh hơn rõ.
3. Bộ nhớ: hai mảng $10^7$ số int (spf, cnt) khoảng 80 MB, trong giới hạn 1 GB của đề.
4. Đọc dữ liệu bằng fread vì có tới khoảng $6 \cdot 10^5$ số.

Không gian$O(M + N + Q)$, $M = 10^7$

Thời gian$O(M \log\log M + (N + Q)\log M + Q \log N)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.700s – full điểm. Phần sàng tới $10^7$ chiếm khoảng 0,15–0,2 giây. Bản mình nộp lên tinhoctre.vn dùng sàng tuyến tính, LCA Tarjan offline và mảng phẳng (CSR) thay cho vector lồng nhau nên chỉ khoảng 0,3 giây trên máy mình. Cách 3 mình không viết bản Python: riêng việc sàng $10^7$ phần tử bằng Python đã mất vài giây.

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
1. Đi trên đường đi	C++	12/20	4.006s	30 điểm (theo subtask)
1. Đi trên đường đi	Python	7/20	3.943s	30 điểm (theo subtask)
2. x = 2^e, đếm tiền tố	C++	8/20	0.348s	30 điểm (theo subtask)
2. x = 2^e, đếm tiền tố	Python	2/20	2.997s	0 điểm (theo subtask)
3. Lũy thừa nguyên tố + DFS offline	C++	20/20	0.700s	100 điểm (theo subtask)

Ghi chú của mình: thời gian là thời gian CPU trên máy mình (máy dùng chung đang khá tải), giới hạn 1 giây; điểm tính theo subtask. Ba kỹ thuật đáng nhớ: (1) $\min(e_p(A), e)$ $= \#\{k \le e : p^k \mid A\}$ – biến min thành phép đếm; (2) đếm trên đường đi bằng $f(u) + f(v) - f(\text{lca}) - f(\text{par(lca)})$; (3) khi không lưu nổi $f_q$ cho mọi đỉnh, hãy gắn truy vấn vào đỉnh rồi DFS một lần, vào thì cộng ra thì trừ. Lời giải chính thức đã đạt 100/100 trên tinhoctre.vn.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇