← 返回题目列表

Codeforces · 990/G

G. GCD 计数

中文机器翻译题面 查看原题

给你一棵由 $$$n$$$ 个顶点组成的树。每个顶点上都写有一个数字;顶点 $$$i$$$ 上的数字等于 $$$a_i$$$。

让我们将函数 $$$g(x, y)$$$ 表示为属于从顶点 $$$x$$$ 到顶点 $$$y$$$(包括这两个顶点)的简单路径的顶点上所写的数字的最大公约数。

对于从 $$$1$$$ 到 $$$2 \cdot 10^5$$$ 的每个整数,你必须计算 $$$(x, y)$$$ $$$(1 \le x \le y \le n)$$$ 的数量,使得 $$$g(x, y)$$$ 等于这个数字。

输入

第一行包含一个整数 $$$n$$$ — 顶点数 $$$(1 \le n \le 2 \cdot 10^5)$$$。

第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ $$$(1 \le a_i \le 2 \cdot 10^5)$$$ — 写在顶点上的数字。

接下来是 $$$n - 1$$$ 行,每行包含两个整数 $$$x$$$ 和 $$$y$$$ $$$(1 \le x, y \le n, x \ne y)$$$ 表示连接顶点 $$$x$$$ 与顶点 $$$y$$$ 的边。保证这些边形成一棵树。

输出

对于从 $$$1$$$ 到 $$$2 \cdot 10^5$$$ 的每个整数 $$$i$$$ 执行以下操作:如果没有一对 $$$(x, y)$$$ 使得 $$$x \le y$$$ 且 $$$g(x, y) = i$$$,则不输出任何内容。否则输出两个整数:$$$i$$$ 和上述对的数量。您必须按升序考虑 $$$i$$$ 的值。

请参阅示例以更好地理解。

示例

输入 #1

3
1 2 3
1 2
2 3

输出 #1

1 4
2 1
3 1

输入 #2

6
1 2 4 8 16 32
1 6
6 3
3 4
4 2
6 5

输出 #2

1 6
2 5
4 6
8 1
16 2
32 1

输入 #3

4
9 16 144 6
1 3
2 3
4 3

输出 #3

1 1
2 1
3 1
6 2
9 2
16 2
144 1