列表

详情


NC213849. [CSP2020]优秀的拆分(power)

描述

题目数据为官方数据,可以提交测试,结果仅供参考,不代表官方成绩,最终成绩以官方发布的最终成绩为准。
一般来说,一个正整数可以拆分成若干个正整数的和。例如, 等。
对于正整数  的一种特定拆分,我们称它为“优秀的”,当且仅当在这种拆分下, 被分解为了若干个不同的  的正整数次幂。注意,一个数  能被表示成  的正整数次幂,当且仅当  能通过正整数个  相乘在一起得到。
例如, 是一个优秀的拆分。但是, 就不是一个优秀的拆分,因为  不是  的正整数次幂。
现在,给定正整数 ,你需要判断这个数的所有拆分中,是否存在优秀的拆分。若存在,请你给出具体的拆分方案。

输入描述

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

输出描述

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

示例1

输入:

6

输出:

4 2

说明:

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

示例2

输入:

7

输出:

-1

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

Python3(3.9) 解法, 执行用时: 19ms, 内存消耗: 2668K, 提交时间: 2020-11-11 07:40:40

s = list(map(int, bin(int(input()))[2:]))[::-1]
print(-1 if s[0] else ' '.join([str((1<<i)*s[i]) for i in range(1,len(s))][::-1]).replace(' 0', ''))

C++(clang++11) 解法, 执行用时: 3ms, 内存消耗: 500K, 提交时间: 2020-11-14 20:42:27

#include<cstdio>
int main(){
	int n;scanf("%d",&n);
	if(n&1)puts("-1");
	else for(int i=28;i;i--)if(n>>i&1)printf("%d ",1<<i);
}

上一题