Become Big For Me
Contest: Codeforces Round 796 (Div. 1)
Difficulty rating: 3500
Tags: combinatorics, constructive algorithms, greedy, math, number theory

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$$$ operations ($$$\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.

Input format:
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.

Output format:
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}$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
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$$$.

Example input:
3
6 10 15

Example output:
1
0 3 1 2 3

Example input:
4
2 4 8 16

Example output:
2
0 1 4
1 1 1

Editorial:
Let $$$f_p(x)$$$ be the maximum integer satisfying $$$p^{f_p(x)}|x$$$.
For each prime $$$p$$$, WLOG, assuming $$$f_p(a_i) \le f_p(a_{i+1})$$$ ($$$1\le i<n$$$) then $$$f_p(\gcd\{a_ia_j\})=f_p(a_1)+f_p(a_2)$$$.
Considering Inclusion-Exclusion Principle:
$$$k\text{-th}\min\{S\}=\sum\limits_{\varnothing\ne T\subseteq S}(-1)^{|T|-k}\tbinom{|T|-1}{k-1}\max\{T\}$$$.
So $$$f_p(\gcd\{a_ia_j\})=\sum\limits_{\varnothing\ne T\subseteq \{f_p(a)\}}((-1)^{|T|-1}+(-1)^{|T|}(|T|-1))\max\{T\}=\sum\limits_{\varnothing\ne T\subseteq \{f_p(a)}(-1)^{|T|}(|T|-2)\max\{T\}$$$.
Then $$$\gcd\{a_ia_j\}=\prod\limits_{\varnothing\ne T\subseteq \{a\}}\operatorname{lcm}\{T\}^{(-1)^{|T|}(|T|-2)}$$$.
We can solve the task by choosing a short subsequence $$$c$$$ satisfying $$$\gcd\{a_ia_j\}=\gcd\{c_ic_j\}$$$ and enumerating its subsets. To fit in the constraint, the length of $$$c$$$ should be no longer than $$$14$$$.
Think of an easier task: choose a small subset $$$g(a)$$$ satisfying $$$\gcd\{a\}=\gcd g(a)$$$. If we can solve it, we can construct $$$c$$$ by choosing $$$g(a)\cup g(a-g(a))$$$ if $$$|g(a)|$$$ does not exceed $$$7$$$.
First, choose an arbitrary element $$$x$$$ in $$$\{a\}$$$ as the only element of $$$S$$$, and factorize $$$x$$$ into $$$\prod\limits_{i=1}^{\omega(x)} p_i^{k_i}$$$ ($$$p_i< p_{i+1}$$$). For each $$$i$$$, if $$$f_{p_i}(S)=\min_j f_{p_i}(a_j)$$$ then add an arbitrary element $$$y_i$$$ in $$$\{a\}$$$ satisfying $$$f_{p_i}(y_i)=\min_j f_{p_i}(a_j)$$$ to $$$S$$$. Now obviously $$$\gcd S=\gcd \{a\}$$$, but $$$|S|\le\omega(x)+1\le 8$$$. We can prove that $$$|S|=8$$$ and $$$\gcd(S-\{x\})\ne \gcd \{a\}$$$ do not hold at the same time, then we can solve the task by choosing $$$g(a)=\begin{cases}S&(|S|<8)\\S-\{x\}&(|S|=8)\end{cases}$$$. Consider the necessary condition of $$$|S|=\omega(x)=8\land\gcd(S-\{x\})\ne \gcd \{a\}$$$: $$$\exist d\in\text{Prime}, f_{d}(x)<\min\limits_{y\in S-\{x\}}f_{d}(y)$$$. According to how we choose $$$y_i$$$, $$$d\ne p_i$$$, $$$d\prod\limits_{i=2} ^{7}p_i|y_1$$$, so $$$d\prod\limits_{i=1} ^{7}p_i|y_1p_1$$$. Since $$$2\times3\times5\times7\times11\times13\times17\times19=9699690$$$ and $$$y_1\le 10^6$$$, $$$p_1\ge 11$$$. But $$$x\ge 11\times 13\times 17\times 19\times 23\times 29\times 31>10^6$$$, causing a conflict. So $$$|S|=\omega(x)=8\land\gcd(S-\{x\})\ne \gcd \{a\}$$$ won't hold.
Up to here, the task is solved.
Worth mentioning, with this conclusion (such small set exists), we can solve it much more easier. Just choose a small set by greedy, and enumerate its subset of size $$$14$$$.