E. Weird LCM Operations
brute force; constructive algorithms; number theory
Given an integer \(n\), you construct an array \(a\) of \(n\) integers, where \(a_i = i\) for all integers \(i\) in the range \([1, n]\). An operation on this array is defined as follows: Select three distinct indices \(i\), \(j\), and \(k\) from the array, and let \(x = a_i\), \(y = a_j\), and \(z = a_k\). Update the array as follows: \(a_i = \operatorname{lcm}(y, z)\), \(a_j = \operatorname{lcm}(x, z)\), and \(a_k = \operatorname{lcm}(x, y)\), where \(\operatorname{lcm}\) represents the least common multiple. Your task is to provide a possible sequence of operations, containing at most \(\lfloor \frac{n}{6} \rfloor + 5\) operations such that after executing these operations, if you create a set containing the greatest common divisors (GCDs) of all subsequences with a size greater than \(1\), then all numbers from \(1\) to \(n\) should be present in this set.After all the operations \(a_i \le 10^{18}\) should hold for all \(1 \le i \le n\).We can show that an answer always exists.
The first line contains one integer \(t\) (\(1 \le t \le 10^2\)) — the number of test cases. The description of the test cases follows.The first and only line of each test case contains an integer \(n\) (\(3 \leq n \leq 3 \cdot 10^{4}\)) — the length of the array.It is guaranteed that the sum of \(n\) over all test cases does not exceed \(3 \cdot 10^{4}\).
The first line should contain an integer \(k\) (\(0 \leq k \leq \lfloor \frac{n}{6} \rfloor + 5\)) — where \(k\) is the number of operations.The next \(k\) lines should contain the description of each operation i.e. \(3\) integers \(i\), \(j\) and \(k\), where \(1 \leq i, j, k \leq n\) and all must be distinct.
In the third test case, \(a = [1, 2, 3, 4, 5, 6, 7]\).First operation:\(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, \color{red}{15}]\).Second operation:\(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}, \color{red}{42}]\).Third operation:\(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]\).Subsequences whose GCD equal to \(i\) is as follows:\(\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\)