Дано дерево из \(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
4500 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач