← 返回题目列表

Codeforces · 1934/E

E. 奇怪的 LCM 操作

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

给定一个整数 $$$n$$$,您可以构造一个由 $$$n$$$ 整数组成的数组 $$$a$$$,其中 $$$a_i = i$$$ 对于 $$$[1, n]$$$ 范围内的所有整数 $$$i$$$。对该数组的操作定义如下:

- 从数组中选择三个不同的索引 $$$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}$$$ 表示最小公倍数。

在所有操作之后,$$$a_i \le 10^{18}$$$ 对于所有 $$$1 \le i \le n$$$ 应该成立。

我们可以证明答案总是存在的。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 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$$$ 是操作数。

接下来的 $$$k$$$ 行应包含每个操作的描述,即 $$$3$$$ 整数 $$$i$$$、$$$j$$$ 和 $$$k$$$,其中 $$$1 \leq i, j, k \leq n$$$ 且全部必须不同。

示例

输入 #1

3
3
4
7

输出 #1

1
1 2 3
1
1 3 4
3
3 5 7
5 6 7
2 3 4

注意

在第三个测试用例中,$$$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, \颜色{红色}{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}, \颜色{红色}{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等于$$$i$$$的子序列如下:

$$$\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$$$