Common Divisor Graph
Contest: Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2)
Difficulty rating: 2700
Tags: 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.

Input format:
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.

Output format:
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}$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
3 3
2 10 3
1 2
1 3
2 3

Example output:
0
1
1

Example input:
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

Example output:
0
1
0
1
0
1
0
1
1
1
1
2

Editorial:
tl;dr - Find initial CCs. Then for every $$$a_i$$$, find prime divisors of $$$a_i+1$$$ and draw new edges of cost 1 between each pair of those primes, and between $$$a_i$$$ and those primes.
Part 1, notation and observations
Two numbers are not coprime iff they have a common prime divisor. Let $$$P(x)$$$ denote distinct prime divisors of $$$x$$$. For example $$$P(100) = \{2, 5\}$$$. You can run prime sieve to find $$$P(x)$$$ for all $$$x \in [2, 10^6 + 1]$$$.
Useful interpretation: Creating $$$a_i \cdot (a_i + 1)$$$ is like creating $$$(a_i + 1)$$$ and drawing an extra edge between $$$a_i$$$ and $$$(a_i + 1)$$$.
Observation: answer doesn't exceed two because you can move between even values. If the starting node isn't even, use one operation to create $$$a_s + 1$$$. If the target node isn't even, use one operation to create $$$a_t + 1$$$. Now you can move between them.
So we just need to check if answer is 0 or 1.
Part 2, checking if answer is 0
Let's find CCs (connected components) of the initial graph. Creates a node for each prime, even if it's not in the input. For each $$$a_i$$$, connect it to all values from $$$P(a_i)$$$. Use DFS or DSU to find CCs.
Given a query, check if two nodes belong to the same CC. If so, the answer is 0.
Part 3, checking if answer is 1.
Let's say that $$$a_s$$$ and $$$a_t$$$ belong to two different CC, denoted cc1 and cc2. The answer is 1 in three cases: we spend one operation on a node from cc1, or a node from cc2, or a node from a completely different CC. The last case is needed e.g. for input $$$n = 3$$$, $$$a = (3, 7, 20)$$$. You need to replicate $$$20$$$ into $$$21$$$ in order to make $$$3$$$ and $$$7$$$ reachable from one another.
For every $$$a_i$$$, let's consider replicating it into $$$a_i + 1$$$. Let's draw new edges of cost 1 between CC of $$$a_i$$$ and all CCs of values $$$P(a_i + 1)$$$.
In the drawing, gray areas are initial CCs. Green edges have cost 1. For example, 9 can create 10, so we connect the whole CC with (9, 21, 27, 33) with the whole CC of prime 5, which contains the input value (25). You can't get from 169 to 9 with cost though. That would be possible if 25 replicated into 26 would be connected to both (9, 21, 27, 33) and to (169). To consider such cases, we need to draw green edges between all pairs of $$$P(a_i + 1)$$$ too.
For example, if $$$a_i = 9$$$, then $$$P(a_i + 1) = \{2, 5\}$$$ so we draw green edges 2-5, 2-3, 3-5.
Given a query, check if there is a green edge between the two CCs. If so, the answer is 1.
—
(should be in spoiler tags) A note about the worst case and preparing tests. One type of max tests is created by choosing $$$n$$$ values $$$x \leq 10^6$$$ with most distinct prime divisors of $$$x + 1$$$. With few exceptions, that means four or five primes, e.g. $$$2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 = 2310$$$, and on average $$$5 \cdot 4 / 2 = 10$$$ edges of cost 1. It could happen though that choosing such values yields a small number of CCs and thus the solution is actually faster. What if there are some other tests that will make the intended solution significantly slower? In particular, only one CC would mean no edges at all. To check that, we run the intended solution and modified the code of "edges of cost 1" part to pretend that all numbers $$$a_i$$$ are coprime. That requires around 1'700'000 inserts to a set and takes less than 1 second. It's much faster if you use vector and then sort it. This "pretend" part couldn't be used in the testset but it was needed to see that the intended solution can for sure solve any test within TL.