← 返回题目列表

Codeforces · 1978/F

F. 大图

中文机器翻译题面 查看原题

给定一个长度为 $$$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$$$ 个顶点,每个顶点对应于矩阵的一个元素。我们将元素 $$$b_{i, j}$$$ 对应的顶点表示为 $$$(i, j)$$$。
- 我们将在顶点 $$$(i_1, j_1)$$$ 和 $$$(i_2, j_2)$$$ 之间绘制一条边,如果 $$$|i_1 - i_2| + |j_1 - j_2| \le k$$$ 和 $$$\gcd(b_{i_1, j_1}, b_{i_2, j_2}) > 1$$$,其中 $$$\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$$$。

输出

对于每个测试用例,输出一个整数 - 所获得的图中连接分量​​的数量。

示例

输入 #1

6
3 3
3 4 5
3 3
3 4 9
3 2
3 4 9
2 2
2 8
5 3
8 27 5 4 3
4 10
2 2 2 2

输出 #1

3
2
3
1
4
1

注意

在第一个测试用例中,语句中给出了矩阵 $$$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$$$ 的元素对应的所有顶点。

在第四个测试用例中,所有顶点都在一个连接组件中。