← 返回题目列表

Codeforces · 1059/C

C. 序列变换

中文机器翻译题面 查看原题

我们将以下过程称为长度 $$$n$$$ 序列的转换。

如果序列为空,则过程结束。否则,将序列中所有元素的最大公约数 (GCD) 添加到结果中,并从序列中删除一个任意元素。因此,当过程结束时,我们得到了一个 $$$n$$$ 整数序列:每次删除之前序列中所有元素的最大公约数。

给定一个整数序列 $$$1, 2, \dots, n$$$。求其变换的字典顺序最大结果。

如果存在一个索引 $$$i$$$,使得 $$$a_j = b_j$$$ 对于所有 $$$j < i$$$ 和 $$$a_i > b_i$$$。

输入

输入的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$1\le n\le 10^6$$$)。

输出

输出 $$$n$$$ 整数 — 按字典顺序排列的最大转换结果。

示例

输入 #1

3

输出 #1

1 1 3

输入 #2

2

输出 #2

1 2

输入 #3

1

输出 #3

1

注意

在第一个示例中,答案可以通过以下方式实现:

- 追加 GCD$$$(1, 2, 3) = 1$$$,删除 $$$2$$$。
- 追加 GCD$$$(1, 3) = 1$$$,删除 $$$1$$$。
- 追加 GCD$$$(3) = 3$$$,删除 $$$3$$$。

我们得到序列 $$$[1, 1, 3]$$$ 作为结果。