Coprime Path

2 secs 1024 MB

配点 : $400$ 点

問題文

$N$ 頂点からなる木が与えられます。 $i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を繋いでいます。また、 $i$ 番目の頂点には正の整数 $A_i$ が書かれています。

パス $\{ v_1, \ldots , v_n \}$ が次の条件を満たすとき、そのパスは Coprime Path であると定義します。

頂点の組 $(L, R) \ (1 \leq L < R \leq N)$ のうち、頂点 $L$ から頂点 $R$ への最短パス $\{ L, \ldots , R \}$ が Coprime Path であるものの個数を求めてください。

ただし、 $\mathrm{gcd}(a_1, \ldots , a_n)$ は $\{ a_1, \ldots , a_n \}$ の最大公約数を表します。

入力は以下の形式で標準入力から与えられます。

$N$
$A_1 \ A_2 \ \cdots \ A_N$
$u_1 \ v_1$
$u_2 \ v_2$
$\vdots$
$u_{N-1} \ v_{N-1}$

頂点の組 $(L, R) \ (1 \leq L < R \leq N)$ のうち、頂点 $L$ から頂点 $R$ への最短パス $\{ L, \ldots , R \}$ が Coprime Path であるものの個数を出力してください。

頂点の組 $(L, R)$ として次の $3$ 通りがあります。

$(L, R) = (1, 2)$ のとき、 $\mathrm{gcd}(A_1, A_2) = \mathrm{gcd}(1, 2) = 1$
$(L, R) = (1, 3)$ のとき、 $\mathrm{gcd}(A_1, A_3) = \mathrm{gcd}(1, 3) = 1$
$(L, R) = (2, 3)$ のとき、 $\mathrm{gcd}(A_2, A_1, A_3) = \mathrm{gcd}(2, 1, 3) = 1$

このうち、 $\mathrm{gcd}$ が $1$ となる頂点の組は $3$ つあります。よって、答えは $3$ です。

頂点の組 $(L, R)$ として次の $10$ 通りがあります。

$(L, R) = (1, 2)$ のとき、 $\mathrm{gcd}(A_1, A_2) = \mathrm{gcd}(6, 2) = 2$
$(L, R) = (1, 3)$ のとき、 $\mathrm{gcd}(A_1, A_3) = \mathrm{gcd}(6, 3) = 3$
$(L, R) = (1, 4)$ のとき、 $\mathrm{gcd}(A_1, A_4) = \mathrm{gcd}(6, 4) = 2$
$(L, R) = (1, 5)$ のとき、 $\mathrm{gcd}(A_1, A_4, A_5) = \mathrm{gcd}(6, 4, 1) = 1$
$(L, R) = (2, 3)$ のとき、 $\mathrm{gcd}(A_2, A_1, A_3) = \mathrm{gcd}(2, 6, 3) = 1$
$(L, R) = (2, 4)$ のとき、 $\mathrm{gcd}(A_2, A_1, A_4) = \mathrm{gcd}(2, 6, 4) = 2$
$(L, R) = (2, 5)$ のとき、 $\mathrm{gcd}(A_2, A_1, A_4, A_5) = \mathrm{gcd}(2, 6, 4, 1) = 1$
$(L, R) = (3, 4)$ のとき、 $\mathrm{gcd}(A_3, A_1, A_4) = \mathrm{gcd}(3, 6, 4) = 1$
$(L, R) = (3, 5)$ のとき、 $\mathrm{gcd}(A_3, A_1, A_4, A_5) = \mathrm{gcd}(3, 6, 4, 1) = 1$
$(L, R) = (4, 5)$ のとき、 $\mathrm{gcd}(A_4, A_5) = \mathrm{gcd}(4, 1) = 1$

このうち、 $\mathrm{gcd}$ が $1$ となる頂点の組は $6$ つあります。よって、答えは $6$ です。

10
3 1 4 1 5 9 2 6 5 3
1 2
1 3
1 8
3 4
3 5
5 6
5 7
8 9
8 10

登録なしで提出できます。

Go (1.21)