A14399. Common Divisor Graph
编程题
普及/提高-
知识点
题目描述
Consider a sequence of distinct integers $a_1, \ldots, a_n$ , each representing one node of a graph. There is an edge between two nodes if the two values are not coprime, i. e. they have a common divisor greater than $1$ .
There are $q$ queries, in each query, you want to get from one given node $a_s$ to another $a_t$ . In order to achieve that, you can choose an existing value $a_i$ and create new value $a_{n+1} = a_i \cdot (1 + a_i)$ , with edges to all values that are not coprime with $a_{n+1}$ . Also, $n$ gets increased by $1$ . You can repeat that operation multiple times, possibly making the sequence much longer and getting huge or repeated values. What's the minimum possible number of newly created nodes so that $a_t$ is reachable from $a_s$ ?
Queries are independent. In each query, you start with the initial sequence $a$ given in the input.
There are $q$ queries, in each query, you want to get from one given node $a_s$ to another $a_t$ . In order to achieve that, you can choose an existing value $a_i$ and create new value $a_{n+1} = a_i \cdot (1 + a_i)$ , with edges to all values that are not coprime with $a_{n+1}$ . Also, $n$ gets increased by $1$ . You can repeat that operation multiple times, possibly making the sequence much longer and getting huge or repeated values. What's the minimum possible number of newly created nodes so that $a_t$ is reachable from $a_s$ ?
Queries are independent. In each query, you start with the initial sequence $a$ given in the input.
输入格式
The first line contains two integers $n$ and $q$ ( $2 \leq n \leq 150\,000$ , $1 \leq q \leq 300\,000$ ) — the size of the sequence and the number of queries.
The second line contains $n$ distinct integers $a_1, a_2, \ldots, a_n$ ( $2 \leq a_i \leq 10^6$ , $a_i \neq a_j$ if $i \ne j$ ).
The $j$ -th of the following $q$ lines contains two distinct integers $s_j$ and $t_j$ ( $1 \leq s_j, t_j \leq n$ , $s_j \neq t_j$ ) — indices of nodes for $j$ -th query.
The second line contains $n$ distinct integers $a_1, a_2, \ldots, a_n$ ( $2 \leq a_i \leq 10^6$ , $a_i \neq a_j$ if $i \ne j$ ).
The $j$ -th of the following $q$ lines contains two distinct integers $s_j$ and $t_j$ ( $1 \leq s_j, t_j \leq n$ , $s_j \neq t_j$ ) — indices of nodes for $j$ -th query.
输出格式
Print $q$ lines. The $j$ -th line should contain one integer: the minimum number of new nodes you create in order to move from $a_{s_j}$ to $a_{t_j}$ .
输入输出样例
输入 #1
3 3 2 10 3 1 2 1 3 2 3
输出 #1
0 1 1
输入 #2
5 12 3 8 7 6 25 1 2 1 3 1 4 1 5 2 1 2 3 2 4 2 5 3 1 3 2 3 4 3 5
输出 #2
0 1 0 1 0 1 0 1 1 1 1 2
说明/提示
In the first example, you can first create new value $2 \cdot 3 = 6$ or $10 \cdot 11 = 110$ or $3 \cdot 4 = 12$ . None of that is needed in the first query because you can already get from $a_1 = 2$ to $a_2 = 10$ .
In the second query, it's optimal to first create $6$ or $12$ . For example, creating $6$ makes it possible to get from $a_1 = 2$ to $a_3 = 3$ with a path $(2, 6, 3)$ .
In the last query of the second example, we want to get from $a_3 = 7$ to $a_5 = 25$ . One way to achieve that is to first create $6 \cdot 7 = 42$ and then create $25 \cdot 26 = 650$ . The final graph has seven nodes and it contains a path from $a_3 = 7$ to $a_5 = 25$ .
In the second query, it's optimal to first create $6$ or $12$ . For example, creating $6$ makes it possible to get from $a_1 = 2$ to $a_3 = 3$ with a path $(2, 6, 3)$ .
In the last query of the second example, we want to get from $a_3 = 7$ to $a_5 = 25$ . One way to achieve that is to first create $6 \cdot 7 = 42$ and then create $25 \cdot 26 = 650$ . The final graph has seven nodes and it contains a path from $a_3 = 7$ to $a_5 = 25$ .