Дано дерево из $$$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$$$. Гарантируется, что эти ребра задают дерево.
Для каждого целого числа $$$i$$$ от $$$1$$$ до $$$2 \cdot 10^5$$$ необходимо сделать следующее: если не существует таких пар $$$(x, y)$$$, что $$$x \le y$$$ и $$$g(x, y) = i$$$, не выводите ничего; иначе выведите два числа: $$$i$$$ и количество описанных пар. Значения $$$i$$$ нужно выводить в возрастающем порядке.
Посмотрите примеры для лучшего понимания.
3
1 2 3
1 2
2 3
1 4
2 1
3 1
6
1 2 4 8 16 32
1 6
6 3
3 4
4 2
6 5
1 6
2 5
4 6
8 1
16 2
32 1
4
9 16 144 6
1 3
2 3
4 3
1 1
2 1
3 1
6 2
9 2
16 2
144 1
Название |
---|