Problem: Excellent Decomposition of an Integer / 优秀的拆分

版权信息： CCF-CSP-J

---

任务总览

任务名称	时间限制	内存限制	分数
优秀的拆分	1 sec	1024 MB	5 points

---

题目描述

一个正整数可以拆分成若干个正整数的和。对于正整数 n 的一种特定拆分，我们称它为“优秀的”，当且仅当在这种拆分下，n 被分解为若干个不同的 2 的正整数次幂。具体来说，n 被表示成若干个不同的数，每个数是 2 的正整数次幂，例如 2^1, 2^2, 2^3 等。

你需要判断给定的整数 n 是否存在一种优秀的拆分。如果存在，输出这种拆分中的每一个数，要求从大到小排列；如果不存在，则输出 -1。

---

输入格式

• 输入只有一行，一个整数 n，表示需要判断的数。

---

输出格式

• 如果存在优秀的拆分，输出该拆分中的所有数，按从大到小的顺序排列，每个数之间用空格隔开。
• 如果不存在优秀的拆分，输出 -1。

---

样例输入

输入示例 1

6

输出示例 1

4 2

输入示例 2

7

输出示例 2

-1

---

输入示例 3

10

输出示例 3

8 2

题目分析与解法

1. ​二进制表示法​：
   • n 的二进制表示中的每一位对应一个 2 的幂次（例如 2^0, 2^1, 2^2 等）。因此，n 的二进制中每个 1 对应一个 2^k（k为正整数）。例如，6 的二进制表示是 110，表示它可以拆分为 4 + 2。
2. ​贪心算法​：
   • 由于我们要求从大到小输出拆分数，因此我们可以从最大的 2 的正整数次幂开始，逐步减去这个数直到 n 为 0。
   • 这个过程类似于将 n 的二进制形式中的每个 1 转换成相应的 2^k。
3. ​步骤​：
   • 找到 n 的每个非零位的二进制表示，从最大位开始进行拆分。
   • 如果 n 不能通过这样的拆分得到结果，则输出 -1。

---

时间复杂度分析

步骤	复杂度
查找 2 的幂次	O(log n)
拆分过程
总复杂度	O(log n)

由于 n 最大为 10^7，log(n) 的最大值大约是 24，因此复杂度 O(log n) 是可以接受的。

---

结论

1. 通过逐步查找 n 的每个 2 的正整数次幂，利用贪心算法可以快速得到拆分方案。
2. 若拆分成功，输出拆分数；否则，输出 -1。