CF1470B Strange Definition

我们称两个整数 $x$ 和 $y$ 是相邻的，如果 $\frac{lcm(x, y)}{gcd(x, y)}$ 是一个完全平方数。例如，$3$ 和 $12$ 是相邻的，但 $6$ 和 $9$ 不是。 这里 $gcd(x, y)$ 表示整数 $x$ 和 $y$ 的[最大公约数（GCD）](https://en.wikipedia.org/wiki/Greatest_common_divisor)，$lcm(x, y)$ 表示整数 $x$ 和 $y$ 的[最小公倍数（LCM）](https://en.wikipedia.org/wiki/Least_common_multiple)。 给定一个长度为 $n$ 的数组 $a$。每一秒，数组中的每个元素 $a_i$ 都会被替换为与当前值相邻的所有元素（包括它自身）的乘积。 令 $d_i$ 表示与 $a_i$ 相邻的元素个数（包括 $a_i$ 自身）。数组的美丽值定义为 $\max_{1 \le i \le n} d_i$。 你会得到 $q$ 个询问：每个询问由一个整数 $w$ 描述，你需要输出经过 $w$ 秒后的数组美丽值。

第一行输入一个整数 $t$（$1 \le t \le 10^5$）——表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 3 \times 10^5$）——数组的长度。 接下来一行包含 $n$ 个整数 $a_1, \ldots, a_n$（$1 \le a_i \le 10^6$）——数组元素。 下一行包含一个整数 $q$（$1 \le q \le 3 \times 10^5$）——询问的数量。 接下来的 $q$ 行，每行包含一个整数 $w$（$0 \le w \le 10^{18}$）——表示每个询问。 保证所有测试用例中 $n$ 的总和不超过 $3 \times 10^5$，所有测试用例中 $q$ 的总和不超过 $3 \times 10^5$。

对于每个询问，输出一个整数，表示对应时刻数组的美丽值。

在第一个测试用例中，初始数组为 $[6, 8, 4, 2]$。在该数组中，元素 $a_4=2$ 与 $a_4=2$ 相邻（因为 $\frac{lcm(2, 2)}{gcd(2, 2)}=\frac{2}{2}=1=1^2$），也与 $a_2=8$ 相邻（因为 $\frac{lcm(8,2)}{gcd(8, 2)}=\frac{8}{2}=4=2^2$）。因此 $d_4=2$，这是该数组中 $d_i$ 的最大值。 在第二个测试用例中，初始数组为 $[12, 3, 20, 5, 80, 1]$。与 $12$ 相邻的元素为 $\{12, 3\}$，与 $3$ 相邻的元素为 $\{12, 3\}$，与 $20$ 相邻的元素为 $\{20, 5, 80\}$，与 $5$ 相邻的元素为 $\{20, 5, 80\}$，与 $80$ 相邻的元素为 $\{20, 5, 80\}$，与 $1$ 相邻的元素为 $\{1\}$。经过一秒后，数组变为 $[36, 36, 8000, 8000, 8000, 1]$。 由 ChatGPT 4.1 翻译