GCD Counting

题意翻译

有一棵有 $n$ 个节点的树，第 $i$ 个节点有点权 $a_i$。 定义 $g(x,y)$ 为 $x$ 到 $y$ 的树上路径所经过的点的点权 $\gcd$。 对于每一个正整数 $k\in[1,2\times 10^5]$ 求出满足以下条件的 $x,y$ 的对数: + $1\le x\le y\le n$ + $g(x,y)=k$ $1\le n,a_i\le 2\times 10^5$

题目描述

You are given a tree consisting of $ n $ vertices. A number is written on each vertex; the number on vertex $ i $ is equal to $ a_i $ . Let's denote the function $ g(x, y) $ as the greatest common divisor of the numbers written on the vertices belonging to the simple path from vertex $ x $ to vertex $ y $ (including these two vertices). For every integer from $ 1 $ to $ 2 \cdot 10^5 $ you have to count the number of pairs $ (x, y) $ $ (1 \le x \le y \le n) $ such that $ g(x, y) $ is equal to this number.

输入输出格式

输入格式

The first line contains one integer $ n $ — the number of vertices $ (1 \le n \le 2 \cdot 10^5) $ . The second line contains $ n $ integers $ a_1 $ , $ a_2 $ , ..., $ a_n $ $ (1 \le a_i \le 2 \cdot 10^5) $ — the numbers written on vertices. Then $ n - 1 $ lines follow, each containing two integers $ x $ and $ y $ $ (1 \le x, y \le n, x \ne y) $ denoting an edge connecting vertex $ x $ with vertex $ y $ . It is guaranteed that these edges form a tree.

输出格式

For every integer $ i $ from $ 1 $ to $ 2 \cdot 10^5 $ do the following: if there is no pair $ (x, y) $ such that $ x \le y $ and $ g(x, y) = i $ , don't output anything. Otherwise output two integers: $ i $ and the number of aforementioned pairs. You have to consider the values of $ i $ in ascending order. See the examples for better understanding.

输入输出样例

输入样例 #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

题意翻译

有一棵有 $n$ 个节点的树，第 $i$ 个节点有点权 $a_i$。 定义 $g(x,y)$ 为 $x$ 到 $y$ 的树上路径所经过的点的点权 $\gcd$。 对于每一个正整数 $k\in[1,2\times 10^5]$ 求出满足以下条件的 $x,y$ 的对数: + $1\le x\le y\le n$ + $g(x,y)=k$ $1\le n,a_i\le 2\times 10^5$