Become Big For Me

题意翻译

> 『来吧，让我们构筑起一个不会遗弃弱者的乐园吧！』——少名针妙丸&鬼人正邪，《东方辉针城》 针妙丸有一个万宝槌，可以将物体变大或者变小。她现在在对一个序列 $a$ 测试这一功能。具体而言，她有一个实数 $v=1$，她希望在不超过 $10^5$ 次操作后，将 $v$ 变为 $\gcd \limits_{i \neq j} \{a_i \times a_j\}$。其中，$\gcd \limits_{i \neq j} \{a_i \times a_j\}$ 指的是，序列 $a$ 中两个不同元素相乘得到的所有乘积的最大公约数。 在每一次操作中，针妙丸可以选择序列 $a$ 中的一个子序列 $b$，并且对其做如下两种操作中的一个： - 放大：令 $v \leftarrow v \times \operatorname{lcm(b)}$； - 缩小：令 $v \leftarrow \dfrac{v}{\operatorname{lcm(b)}}$。 其中，$\operatorname{lcm(b)}$ 指的是序列 $b$ 中所有元素的最小公倍数。此外，她不要求 $v$ 一定是个整数，也就是说执行缩小操作的时候，$v$ 可以不是 $\operatorname{lcm(b)}$ 的倍数。 更进一步地说，针妙丸希望她选取的所有子序列 $b$ 的长度不超过 $10^6$，即 $\sum |b| \leq 10^6$。请你为她找到一种操作方案。注意，您无需最小化任何东西。 **输入格式** 第一行输入一个正整数 $n(2 \leq n \leq 10^5)$，表示序列 $a$ 的长度。 第二行输入 $n$ 个正整数 $a_1,a_2,\dots a_n(1 \leq a_i \leq 10^6)$。 保证最后的答案一定存在。 **输出格式** 第一行输出一个正整数 $k$，表示操作次数。 第二行开始往下输出 $k$ 行，每行包含若干个整数。对于每一行，首先输出两个整数 $f \in \{0,1\}$ 和 $p$，其中 $f=0$ 表示执行放大操作，而 $f=1$ 表示执行缩小操作。$p$ 表示所截取的子序列 $b$ 的长度。接下来是 $p$ 个正整数 $i_1,i_2,\dots,i_p(1 \leq i_1<i_2<\dots<i_p \leq n)$，表示所截取的子序列 $b$ 对应原序列 $a$ 的下标。形式化地说，$b_j=a_{i_j}$。

题目描述

Come, let's build a world where even the weak are not forgotten! —Kijin Seija, Double Dealing Characters Shinmyoumaru has a mallet that can turn objects bigger or smaller. She is testing it out on a sequence $ a $ and a number $ v $ whose initial value is $ 1 $ . She wants to make $ v = \gcd\limits_{i\ne j}\{a_i\cdot a_j\} $ by no more than $ 10^5 $ opreations ( $ \gcd\limits_{i\ne j}\{a_i\cdot a_j\} $ denotes the $ \gcd $ of all products of two distinct elements of the sequence $ a $ ). In each operation, she picks a subsequence $ b $ of $ a $ , and does one of the followings: - Enlarge: $ v = v \cdot \mathrm{lcm}(b) $ - Reduce: $ v = \frac{v}{\mathrm{lcm}(b)} $ Note that she does not need to guarantee that $ v $ is an integer, that is, $ v $ does not need to be a multiple of $ \mathrm{lcm}(b) $ when performing Reduce. Moreover, she wants to guarantee that the total length of $ b $ chosen over the operations does not exceed $ 10^6 $ . Fine a possible operation sequence for her. You don't need to minimize anything.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 2\leq n\leq 10^5 $ ) — the size of sequence $ a $ . The second line contains $ n $ integers $ a_1,a_2,\cdots,a_n $ ( $ 1\leq a_i\leq 10^6 $ ) — the sequence $ a $ . It can be shown that the answer exists.

输出格式

The first line contains a non-negative integer $ k $ ( $ 0\leq k\leq 10^5 $ ) — the number of operations. The following $ k $ lines contains several integers. For each line, the first two integers $ f $ ( $ f\in\{0,1\} $ ) and $ p $ ( $ 1\le p\le n $ ) stand for the option you choose ( $ 0 $ for Enlarge and $ 1 $ for Reduce) and the length of $ b $ . The other $ p $ integers of the line $ i_1,i_2,\ldots,i_p $ ( $ 1\le i_1<i_2<\ldots<i_p\le n $ ) represents the indexes of the subsequence. Formally, $ 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

说明

Test case 1: $ \gcd\limits_{i\ne j}\{a_i\cdot a_j\}=\gcd\{60,90,150\}=30 $ . Perform $ v = v\cdot \operatorname{lcm}\{a_1,a_2,a_3\}=30 $ . Test case 2: $ \gcd\limits_{i\ne j}\{a_i\cdot a_j\}=8 $ . Perform $ v = v\cdot \operatorname{lcm}\{a_4\}=16 $ . Perform $ v = \frac{v}{\operatorname{lcm}\{a_1\}}=8 $ .

**题目大意：**
少名针妙丸有一个能放大或缩小物体的万宝槌，她正在对一个序列 $a$ 测试这一功能。她希望将初始值为1的实数 $v$ 变为序列 $a$ 中任意两个不同元素乘积的最大公约数 $\gcd \limits_{i \neq j} \{a_i \times a_j\}$，且操作次数不超过 $10^5$ 次。每次操作，她可以选择序列 $a$ 的一个子序列 $b$，并执行放大或缩小操作。放大操作是 $v \leftarrow v \times \operatorname{lcm}(b)$，缩小操作是 $v \leftarrow \frac{v}{\operatorname{lcm}(b)}$。所有操作的子序列长度之和不超过 $10^6$。需要找到一种操作方案。

**输入格式：**
第一行输入一个正整数 $n(2 \leq n \leq 10^5)$，表示序列 $a$ 的长度。
第二行输入 $n$ 个正整数 $a_1,a_2,\dots a_n(1 \leq a_i \leq 10^6)$。

**输出格式：**
第一行输出一个正整数 $k$，表示操作次数。
接下来 $k$ 行，每行首先输出两个整数 $f \in \{0,1\}$ 和 $p$，$f=0$ 表示放大操作，$f=1$ 表示缩小操作，$p$ 表示子序列 $b$ 的长度。然后输出 $p$ 个正整数，表示子序列 $b$ 对应原序列 $a$ 的下标。**题目大意：** 少名针妙丸有一个能放大或缩小物体的万宝槌，她正在对一个序列 $a$ 测试这一功能。她希望将初始值为1的实数 $v$ 变为序列 $a$ 中任意两个不同元素乘积的最大公约数 $\gcd \limits_{i \neq j} \{a_i \times a_j\}$，且操作次数不超过 $10^5$ 次。每次操作，她可以选择序列 $a$ 的一个子序列 $b$，并执行放大或缩小操作。放大操作是 $v \leftarrow v \times \operatorname{lcm}(b)$，缩小操作是 $v \leftarrow \frac{v}{\operatorname{lcm}(b)}$。所有操作的子序列长度之和不超过 $10^6$。需要找到一种操作方案。 **输入格式：** 第一行输入一个正整数 $n(2 \leq n \leq 10^5)$，表示序列 $a$ 的长度。 第二行输入 $n$ 个正整数 $a_1,a_2,\dots a_n(1 \leq a_i \leq 10^6)$。 **输出格式：** 第一行输出一个正整数 $k$，表示操作次数。 接下来 $k$ 行，每行首先输出两个整数 $f \in \{0,1\}$ 和 $p$，$f=0$ 表示放大操作，$f=1$ 表示缩小操作，$p$ 表示子序列 $b$ 的长度。然后输出 $p$ 个正整数，表示子序列 $b$ 对应原序列 $a$ 的下标。