CF1059C Sequence Transformation

我们将如下过程称为长度为 $n$ 的序列的“变换”： 如果序列为空，则过程结束。否则，将当前序列所有元素的最大公约数（GCD）添加到结果序列中，并从序列中删除一个任意元素。如此反复，直到序列为空。最终，我们会得到一个长度为 $n$ 的整数序列：每次删除元素前，当前序列所有元素的最大公约数。 给定整数序列 $1, 2, \dots, n$，请你求出其变换结果中字典序最大的序列。 如果存在某个下标 $i$，使得对于所有 $j < i$ 都有 $a_j = b_j$，且 $a_i > b_i$，则序列 $a_1, a_2, \ldots, a_n$ 的字典序大于序列 $b_1, b_2, \ldots, b_n$。

输入仅一行，包含一个整数 $n$（$1 \leq n \leq 10^6$）。

输出 $n$ 个整数，表示该变换结果中字典序最大的序列。

在第一个样例中，可以按如下方式实现： - 添加 GCD$(1, 2, 3) = 1$，删除 $2$。 - 添加 GCD$(1, 3) = 1$，删除 $1$。 - 添加 GCD$(3) = 3$，删除 $3$。 最终得到序列 $[1, 1, 3]$。 由 ChatGPT 4.1 翻译