← 返回题目列表

Codeforces · 1687/E

E. 为我而变大

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

Shinmyoumaru 有一个木槌,可以将物体变大或变小。她正在序列 $$$a$$$ 和初始值为 $$$1$$$ 的数字 $$$v$$$ 上进行测试。她想要通过不超过 $$$10^5$$$ 操作来生成 $$$v = \gcd\limits_{i\ne j}\{a_i\cdot a_j\}$$$ ($$$\gcd\limits_{i\ne j}\{a_i\cdot a_j\}$$$ 表示序列中两个不同元素的所有乘积的 $$$\gcd$$$ $$$a$$$)。

在每个操作中,她选择 $$$a$$$ 的子序列 $$$b$$$,并执行以下操作之一:

- 放大:$$$v = v \cdot \mathrm{lcm}(b)$$$
- 减少:$$$v = \frac{v}{\mathrm{lcm}(b)}$$$

注意,她不需要保证$$$v$$$是整数,即执行Reduce时$$$v$$$不需要是$$$\mathrm{lcm}(b)$$$的倍数。

此外,她想保证在操作中选择的 $$$b$$$ 的总长度不超过 $$$10^6$$$。为她确定一个可能的操作顺序。你不需要最小化任何东西。

输入

第一行包含一个整数 $$$n$$$ ($$$2\leq n\leq 10^5$$$) — 序列 $$$a$$$ 的大小。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\cdots,a_n$$$ ($$$1\leq a_i\leq 10^6$$$) — 序列 $$$a$$$。

可以证明答案存在。

输出

第一行包含一个非负整数 $$$k$$$ ($$$0\leq k\leq 10^5$$$) — 操作数。

以下 $$$k$$$ 行包含几个整数。对于每一行,前两个整数 $$$f$$$ ($$$f\in\{0,1\}$$$) 和 $$$p$$$ ($$$1\le p\le n$$$) 代表您选择的选项($$$0$$$ 表示放大,$$$1$$$ 表示缩小)和 $$$b$$$ 的长度。 $$$i_1,i_2,\ldots,i_p$$$ ($$$1\le i_1<i_2<\ldots<i_p\le n$$$) 行的其他 $$$p$$$ 整数表示子序列的索引。形式上,$$$b_j=a_{i_j}$$$。

示例

输入 #1

3
6 10 15

输出 #1

1
0 3 1 2 3

输入 #2

4
2 4 8 16

输出 #2

2
0 1 4
1 1 1

注意

测试用例1:

$$$\gcd\limits_{i\ne j}\{a_i\cdot a_j\}=\gcd\{60,90,150\}=30$$$。

执行 $$$v = v\cdot \operatorname{lcm}\{a_1,a_2,a_3\}=30$$$。

测试用例2:

$$$\gcd\limits_{i\ne j}\{a_i\cdot a_j\}=8$$$。

执行 $$$v = v\cdot \operatorname{lcm}\{a_4\}=16$$$。

执行 $$$v = \frac{v}{\operatorname{lcm}\{a_1\}}=8$$$。