Дано целое число \(n\), вы создаете массив \(a\) из \(n\) целых чисел, где \(a_i = i\) для всех целых чисел \(i\) в диапазоне \([1, n]\). Операция над этим массивом определена следующим образом:
- Выберите в массиве три различных индекса \(i\), \(j\) и \(k\) и присвойте \(x = a_i\), \(y = a_j\) и \(z = a_k\).
- Обновите массив следующим образом: \(a_i = \operatorname{lcm}(y, z)\), \(a_j = \operatorname{lcm}(x, z)\) и \(a_k = \operatorname{lcm}(x, y)\), где \(\operatorname{lcm}\) обозначает наименьшее общее кратное.
Ваша задача предоставить последовательность из не более чем
\(\lfloor \frac{n}{6} \rfloor + 5\) операций таких, что после применения этих операций, если вы возьмете множество, содержащее наибольший общий делитель (НОД) всех подпоследовательностей
размера больше \(1\), то каждое число от
\(1\) до
\(n\) должно принадлежать этому множеству.
После операций должно выполняться \(a_i \le 10^{18}\) для всех \(1 \le i \le n\).
Можно показать, что ответ всегда существует.
Примечание
В третьем наборе входных данных \(a = [1, 2, 3, 4, 5, 6, 7]\).
Первая операция:
\(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}]\).
Вторая операция:
\(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}]\).
Третья операция:
\(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]\).
GCD равное \(i\) может быть получено используя следующие подпоследовательности:
\(\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\)