English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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.
[samples]
给你一棵包含 $n$ 个顶点的树。每个顶点上写有一个数字，顶点 $i$ 上的数字为 $a_i$。
定义函数 $g(x, y)$ 为从顶点 $x$ 到顶点 $y$ 的简单路径上所有顶点（包括 $x$ 和 $y$）所写数字的最大公约数。
对于从 $1$ 到 $2 \dot.op 10^5$ 的每个整数，你需要计算满足 $g(x, y)$ 等于该整数的点对 $(x, y)$（其中 $1 \lt.eq x \lt.eq y \lt.eq n$）的数量。
第一行包含一个整数 $n$ —— 顶点的数量 $(1 \lt.eq n \lt.eq 2 \dot.op 10^5)$。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(1 \lt.eq a_i \lt.eq 2 \dot.op 10^5)$ —— 写在顶点上的数字。
接下来 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$ $(1 \lt.eq x, y \lt.eq n, x \ne y)$，表示连接顶点 $x$ 和顶点 $y$ 的边。保证这些边构成一棵树。
对于从 $1$ 到 $2 \dot.op 10^5$ 的每个整数 $i$，执行以下操作：如果不存在点对 $(x, y)$ 满足 $x \lt.eq y$ 且 $g(x, y) = i$，则不输出任何内容；否则输出两个整数：$i$ 和满足条件的点对数量。你必须按 $i$ 的升序输出。
详见示例以更好地理解。
## Input
第一行包含一个整数 $n$ —— 顶点的数量 $(1 \lt.eq n \lt.eq 2 \dot.op 10^5)$。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(1 \lt.eq a_i \lt.eq 2 \dot.op 10^5)$ —— 写在顶点上的数字。接下来 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$ $(1 \lt.eq x, y \lt.eq n, x \ne y)$，表示连接顶点 $x$ 和顶点 $y$ 的边。保证这些边构成一棵树。
## Output
对于从 $1$ 到 $2 \dot.op 10^5$ 的每个整数 $i$，执行以下操作：如果不存在点对 $(x, y)$ 满足 $x \lt.eq y$ 且 $g(x, y) = i$，则不输出任何内容；否则输出两个整数：$i$ 和满足条件的点对数量。你必须按 $i$ 的升序输出。详见示例以更好地理解。
[samples]
Let $ T = (V, E) $ be a tree with $ |V| = n $, and let $ a: V \to \mathbb{Z}^+ $ be a function assigning a positive integer $ a_i $ to each vertex $ i \in V $.
Define the function $ g(x, y) = \gcd\{ a_v \mid v \in \text{path}(x, y) \} $, where $ \text{path}(x, y) $ denotes the set of vertices on the unique simple path between $ x $ and $ y $ in $ T $, including endpoints.
For each integer $ d \in [1, 2 \cdot 10^5] $, let
$$
f(d) = \left| \left\{ (x, y) \in V \times V \mid x \leq y,\ g(x, y) = d \right\} \right|.
$$
Compute $ f(d) $ for all $ d \in [1, 2 \cdot 10^5] $, and output each pair $ (d, f(d)) $ such that $ f(d) > 0 $, in increasing order of $ d $.
API Response (JSON)
{
"problem": {
"name": "G. GCD Counting",
"description": {
"content": "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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 4000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF990G"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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$.\n\nLet's denote the function $g(x, y)$ as the greatest common divisor of ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "给你一棵包含 $n$ 个顶点的树。每个顶点上写有一个数字，顶点 $i$ 上的数字为 $a_i$。\n\n定义函数 $g(x, y)$ 为从顶点 $x$ 到顶点 $y$ 的简单路径上所有顶点（包括 $x$ 和 $y$）所写数字的最大公约数。\n\n对于从 $1$ 到 $2 \\dot.op 10^5$ 的每个整数，你需要计算满足 $g(x, y)$ 等于该整数的点对 $(x, y)$（其中 $1 \\lt.eq...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ T = (V, E) $ be a tree with $ |V| = n $, and let $ a: V \\to \\mathbb{Z}^+ $ be a function assigning a positive integer $ a_i $ to each vertex $ i \\in V $.\n\nDefine the function $ g(x, y) = \\gcd\\{ ...",
"is_translate": false,
"language": "Formal"
}
]
}