CF1978F.Large Graph

给定一个长度为 $n$ 的数组 $a$。我们构造一个 $n \times n$ 的方阵 $b$，其中第 $i$ 行包含数组 $a$ 向右循环平移 $i-1$ 位后的结果。例如，对于数组 $a = [3, 4, 5]$，得到的矩阵为

$$b = \begin{bmatrix} 3 & 4 & 5 \\ 5 & 3 & 4 \\ 4 & 5 & 3 \end{bmatrix}$$

我们构造如下图：

• 图包含 $n^2$ 个顶点，每个顶点对应矩阵中的一个元素。我们用 $(i, j)$ 表示对应于 $b_{i, j}$ 的顶点。
• 如果满足 $|i_1 - i_2| + |j_1 - j_2| \le k$ 且 $\gcd(b_{i_1, j_1}, b_{i_2, j_2}) > 1$，则在顶点 $(i_1, j_1)$ 和 $(i_2, j_2)$ 之间连一条边，其中 $\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数。

你的任务是计算所得图中的连通分量数目$^{\dagger}$。

$^{\dagger}$ 连通分量指的是图中任意两个顶点都可以通过边互相到达的极大顶点集合，并且加入任何其他顶点都会破坏这个性质。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。接下来是每组测试用例的描述。

每组测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 10^6$，$2 \le k \le 2 \cdot 10^6$），分别表示数组的长度和参数 $k$。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^6$），表示数组 $a$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每组测试用例，输出一个整数，表示所得图中的连通分量数目。

在第一个测试用例中，矩阵 $b$ 如题目描述所示。第一个连通分量包含顶点 $(1, 1)$、$(2, 2)$ 和 $(3, 3)$。第二个连通分量包含顶点 $(1, 2)$、$(2, 3)$ 和 $(3, 1)$。第三个连通分量包含顶点 $(1, 3)$、$(2, 1)$ 和 $(3, 2)$。因此，该图有 $3$ 个连通分量。

在第二个测试用例中，得到的矩阵为：

$$b = \begin{bmatrix} 3 & 4 & 9 \\ 9 & 3 & 4 \\ 4 & 9 & 3 \end{bmatrix}$$

第一个连通分量包含所有值为 $3$ 和 $9$ 的元素对应的顶点。第二个连通分量包含所有值为 $4$ 的元素对应的顶点。

在第四个测试用例中，所有顶点都在同一个连通分量中。

由 ChatGPT 4.1 翻译