G. Common Divisor Graph
brute force; constructive algorithms; dsu; graphs; hashing; math; number theory
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.
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.
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}\).
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\).