当前位置:首页 > 题解目录 > 正文内容

【题解】2020-T1 优秀的拆分

亿万年的星光4年前 (2021-10-04)题解目录1827

【题目描述】

一般来说,一个正整数可以拆分成若干个正整数的和。

例如,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。

【样例输入】

6

【样例输出】

4 2

【提示】

样例解释

6=4+2=22+21是一个优秀的拆分。注意6=2+2+2不是一个优秀的拆分,因为拆分成的3个数不满足每个数互不相同。


【样例输入2】

7


【样例输出2】

-1

【数据规模与约定】

对于20%的数据,n<=10。

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

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

对于80%的数据,n<=1024。

对于100%的数据,1<=n<=1*10^7


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【题解】银行排队

【题目描述】我们大多都有在银行排队的经历,唉,那坑爹的排队啊!现在就让我们来算算我们这些客户平均需要等多久吧。每天刚开始时银行会开m个窗口来为我们total个客户办理业务,当有客户需要办理业务时,先选...

【题解】统计自然数

【题目描述】某次科研调查时得到了n个自然数,每个数均不超过1500000000(1.5*109)。已知不相同的数不超过10000个,现在需要统计这些自然数各自出现的次数,并按照自然数从小到大的顺序输出...

【题解】切比雪夫距离

【题目描述】小C有一个平面!它发现了平面上的两个点,请你求出求它们之间的切比雪夫距离。切比雪夫距离定义为x与y方向坐标差的绝对值较大值。【输入描述】四个整数,a,b,c,d。坐标为(a,b)与(c,d...

【题解】完全背包问题

【题目描述】设有n种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为M,今从n种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于M,而价值的和...

【题解】画百钱买百鸡

【题目描述】鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一,百钱买百鸡。问鸡翁、鸡母、鸡雏各几何?#include<iostream> using namespace ...

【题解】高精度除法

【题目描述】高精除以高精,求它们的商和余数。【输入描述】输入两个低于300位的正整数。【输出描述】输出商和余数。【样例输入】12313123184575776878979876423245678643...