A15110. Become Big For Me
编程题
普及/提高-
知识点
题目描述
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.
—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 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}$ .
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$ .
$\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$ .