-->
当前位置:首页 > 题库 > 正文内容

编程题:优秀的拆分

Luz3年前 (2022-04-08)题库664
一般来说,一个正整数可以拆分成若干个正整数的和。例如,1=1,10=1+2+3+4 等。

对于正整数 n 的一种特定拆分,我们称它为“优秀的”,当且仅当在这种拆分下,n 被分解为了若干个不同的 2 的正整数次幂。注意,一个数 x 能被表示成 2 的正整数次幂,当且仅当 x 能通过正整数个 2 相乘在一起得到。

例如,$$10 = 8 + 2 = 2^3+2^1$$是一个优秀的拆分。但是,$$7 = 4 + 2 + 1 = 2^2+2^1+2^0 $$ 就不是一个优秀的拆分,因为 1 不是 2 的正整数次幂。现在,给定正整数 n,你需要判断这个数的所有拆分中,是否存在优秀的拆分。若存在,请你给出具体的拆分方案。

### 输入格式:

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

### 输出格式:

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

若不存在优秀的拆分,输出“-1”(不包含双引号)。
数据范围与提示
对于 20% 的数据,$n \le 10$。

对于另外 20% 的数据,保证 n 为奇数。

对于另外 20% 的数据,保证 n 为 2 的正整数次幂。

对于 80% 的数据,$$n \le 1024$$。

对于 100% 的数据,$$1 \le n \le 1 \times 10^7$$ 。

### 输入样例:

在这里给出一组输入。例如:

in
6


### 输出样例:

在这里给出相应的输出。例如:

out
4 2

样例解释1
6 = 4 + 2 = $$2^2+2^1 $$是一个优秀的拆分。注意,6=2+2+2不是优秀的拆分,因为拆分成的 3 个数不满足每个数互不相同。





答案:若无答案欢迎评论

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。