CF1934E Weird LCM Operations

给定一个整数 $n$，你需要构造一个长度为 $n$ 的数组 $a$，其中 $a_i = i$，对于所有 $i$ 满足 $1 \leq i \leq n$。对该数组定义如下操作： - 选择数组中的三个不同的下标 $i$、$j$ 和 $k$，令 $x = a_i$，$y = a_j$，$z = a_k$。 - 按如下方式更新数组：$a_i = \operatorname{lcm}(y, z)$，$a_j = \operatorname{lcm}(x, z)$，$a_k = \operatorname{lcm}(x, y)$，其中 $\operatorname{lcm}$ 表示最小公倍数。 你的任务是给出一组操作序列，操作次数不超过 $\lfloor \frac{n}{6} \rfloor + 5$，使得在执行完这些操作后，如果你构造一个集合，集合中包含所有长度大于 $1$ 的子序列的最大公约数（GCD），那么从 $1$ 到 $n$ 的所有整数都应该出现在这个集合中。所有操作结束后，需保证 $1 \leq a_i \leq 10^{18}$ 对于所有 $1 \leq i \leq n$。 可以证明，总是存在满足条件的答案。

第一行包含一个整数 $t$（$1 \leq t \leq 10^2$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$3 \leq n \leq 3 \cdot 10^{4}$），表示数组的长度。 保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^{4}$。

第一行输出一个整数 $k$（$0 \leq k \leq \lfloor \frac{n}{6} \rfloor + 5$），表示操作的次数。 接下来的 $k$ 行，每行输出三个整数 $i$、$j$、$k$，表示一次操作，$1 \leq i, j, k \leq n$ 且三者互不相同。

在第三个测试用例中，$a = [1, 2, 3, 4, 5, 6, 7]$。 第一次操作： $i = 3$，$j = 5$，$k = 7$ $x = 3$，$y = 5$，$z = 7$ $a = [1, 2, \operatorname{lcm}(y,z), 4, \operatorname{lcm}(x,z), 6, \operatorname{lcm}(x,y)] = [1, 2, \color{red}{35}, 4, \color{red}{21}, 6, \color{red}{15}]$ 第二次操作： $i = 5$，$j = 6$，$k = 7$ $x = 21$，$y = 6$，$z = 15$ $a = [1, 2, 35, 4, \operatorname{lcm}(y,z), \operatorname{lcm}(x,z), \operatorname{lcm}(x,y)] = [1, 2, 35, 4, \color{red}{30}, \color{red}{105}, \color{red}{42}]$ 第三次操作： $i = 2$，$j = 3$，$k = 4$ $x = 2$，$y = 35$，$z = 4$ $a = [1, \operatorname{lcm}(y,z), \operatorname{lcm}(x,z), \operatorname{lcm}(x,y), 30, 105, 42] = [1, \color{red}{140}, \color{red}{4}, \color{red}{70}, 30, 105, 42]$ 各个子序列的最大公约数如下： $\gcd(a_1, a_2) = \gcd(1, 140) = 1$ $\gcd(a_3, a_4) = \gcd(4, 70) = 2$ $\gcd(a_5, a_6, a_7) = \gcd(30, 105, 42) = 3$ $\gcd(a_2, a_3) = \gcd(140, 4) = 4$ $\gcd(a_2, a_4, a_5, a_6) = \gcd(140, 70, 30, 105) = 5$ $\gcd(a_5, a_7) = \gcd(30, 42) = 6$ $\gcd(a_2, a_4, a_6, a_7) = \gcd(140, 70, 105, 42) = 7$ 由 ChatGPT 4.1 翻译