【题目链接】

题意

给你一个n，有1-n共n个数字，每次操作求一下剩余数字的最大公因数，再删去一个数字，执行n次操作。
令n次操作的最大公因数排成一个序列，求该序列字典序的最大值

Examples

input
3
output
1 1 3
input
2
output
1 2
input
1
output
1

Note

In the first sample the answer may be achieved this way:

Append GCD(1,2,3)=1(1,2,3)=1, remove 2.
Append GCD(1,3)=1(1,3)=1, remove 1.
Append GCD(3)=3(3)=3, remove 3.
We get the sequence [1,1,3] as the result.

思路

首先在纸上模拟前几项。
1.发现一定是先取走奇数
当n为奇数时，取走n/2+1个奇数(即输出n/2+1个1)，当n为偶数时，取走n/2个奇数(即输出n/2个1)。

当n=16时

第一次后剩余元素 2 4 6 8 10 12 14 16
输出8个1

当前最大公因数为2

此时第九个元素为2，没有其他取法大于当前序列。

2.发现一定是抽空取

当n=16时

第一次后剩余元素 2 4 6 8 10 12 14 16
输出8个1

第二次后剩余元素 4 8 12 16
输出4个2

当前最大公因数为4

此时第13个元素是4，没有其他取法大于当前序列。

3.当n=3或者说当前剩了3个元素

例如 剩余元素 4 8 12
显然第一次取走4，第二次8，第三次12是最优选择。
而我们之前的结论顺序是4，12，8。

所以我们需要在n=3的时候加上特判，判断最后一个元素能否变大(赛时是这样想的，后来发现当n=3时一定是1：1：3的比例，所以这里也可以直接输出)。不过赛时我发现只会影响到最后一个输出，所以特判了最后一个能否倍增来解决。

AC代码

#include <iostream>
using namespace std;
int main()
{
	int n, nn;
	scanf("%d", &n);
	nn = n;
	for (int i = 0; n != 0; i++)
	{
		int a = n / 2;
		int b = n - a;
		for (int j = 0; j < b; j++)
			printf("%d ", 1 << i);
		n = a;
		if (n == 1)
		{
			int t = 1 << i;
			int tt = t;
			while (tt + t <= nn)
				tt += t;
			printf("%d", tt);
			return 0;
		}
	}
}