#D305. 优秀的拆分

优秀的拆分

题目描述:

在数学的数论领域中,对于一个给定的正整数,我们常常会探讨将其拆分为若干个正整数之和的不同方式。 比如,对于数字1,它只能拆分为1本身;而对于数字10,可以拆分成1+2+3+4等多种形式。 在此基础上,我们定义一种特殊的拆分方式 ——“优秀的” 拆分。当且仅当一个正整数n在某种拆分下,被分解为了若干个各不相同的2的正整数次幂时,我们称这种拆分是 “优秀的”。这里需要明确的是,一个数x能够被表示为2的正整数次幂,意味着x可以通过若干个(至少一个)2相乘而得到。 举例来说,对于正整数10,10=8+2=23+2110=8+2=2^3+2^1,这种拆分方式就是 “优秀的”。然而,像7=4+2+1=22+21+207=4+2+1=2^2+2^1+2^0这样的拆分就不符合 “优秀的” 拆分定义,因为其中的1=201=2^0,0并非正整数,即1不是2的正整数次幂。 现在,给定一个正整数n,你的任务是判断在这个数的所有可能拆分中,是否存在 “优秀的” 拆分。如果存在,要求你给出具体的拆分方案。

输入格式:

输入只有一行,一个整数 n,代表需要判断的数。

输出格式:

如果这个数的所有拆分中,存在优秀的拆分。那么,你需要从大到小输出这个拆分中的每一个数,相邻两个数之间用一个空格隔开。可以证明,在规定了拆分数字的顺序后,该拆分方案是唯一的。 若不存在优秀的拆分,输出 -1。

样例:

6
4 2

提示

对于 100% 的数据,1≤n≤10^7。