CF1553G Common Divisor Graph

给定一个由 $n$ 个互不相同的整数 $a_1, \ldots, a_n$ 组成的序列，每个整数代表图中的一个节点。如果两个节点对应的值不互质（即存在大于 $1$ 的公约数），则它们之间有一条边。 有 $q$ 个询问，每个询问要求你从给定的节点 $a_s$ 到另一个节点 $a_t$。为此，你可以选择一个已有的值 $a_i$，并新建一个值 $a_{n+1} = a_i \cdot (1 + a_i)$，该节点与所有与 $a_{n+1}$ 不互质的节点连边。同时，$n$ 增加 $1$。你可以多次进行该操作，序列可能变得很长，且可能出现很大或重复的值。请问，最少需要新建多少个节点，才能使 $a_t$ 从 $a_s$ 可达？ 每个询问相互独立。每次询问都从输入给定的初始序列 $a$ 开始。

第一行包含两个整数 $n$ 和 $q$（$2 \leq n \leq 150\,000$，$1 \leq q \leq 300\,000$）——序列的长度和询问的数量。 第二行包含 $n$ 个互不相同的整数 $a_1, a_2, \ldots, a_n$（$2 \leq a_i \leq 10^6$，如果 $i \ne j$，则 $a_i \ne a_j$）。 接下来的 $q$ 行，每行包含两个不同的整数 $s_j$ 和 $t_j$（$1 \leq s_j, t_j \leq n$，$s_j \ne t_j$），表示第 $j$ 个询问的起点和终点的节点编号。

输出 $q$ 行，每行一个整数，第 $j$ 行表示从 $a_{s_j}$ 到 $a_{t_j}$ 最少需要新建的节点数。

在第一个样例中，你可以先新建 $2 \cdot 3 = 6$ 或 $10 \cdot 11 = 110$ 或 $3 \cdot 4 = 12$。但第一个询问其实不需要新建节点，因为已经可以从 $a_1 = 2$ 到 $a_2 = 10$。 在第二个询问中，最优做法是先新建 $6$ 或 $12$。例如，新建 $6$ 后，可以通过路径 $(2, 6, 3)$ 从 $a_1 = 2$ 到 $a_3 = 3$。 在第二个样例的最后一个询问中，我们希望从 $a_3 = 7$ 到 $a_5 = 25$。一种做法是先新建 $6 \cdot 7 = 42$，再新建 $25 \cdot 26 = 650$。最终图中有七个节点，且存在从 $a_3 = 7$ 到 $a_5 = 25$ 的路径。 由 ChatGPT 4.1 翻译