2548 問題 B: [CSP-J2020] 優(yōu)秀的拆分
時間限制: 1s
內存限制: 128MB 提交: 1305 解決: 549
題目描述
一般來說，一個正整數可以拆分成若干個正整數的和。例如，1 = 1，10 = 1 + 2 + 3 + 4 等。
對于正整數 n 的一種特定拆分，我們稱它為“優(yōu)秀的”，當且僅當在這種拆 分下，n 被分解為了若干個不同的 2 的正整數次冪。注意，一個數 x 能被表 示成 2 的正整數次冪，當且僅當 x 能通過正整數個 2 相乘在一起得到。
例如，10 = 8 + 2 = 23 + 21 是一個優(yōu)秀的拆分。但是，7 = 4 + 2 + 1 = 22 + 21 + 20 就不是一個優(yōu)秀的拆分，因為 1 不是 2 的正整數次冪。
現在，給定正整數 n，你需要判斷這個數的所有拆分中，是否存在優(yōu)秀的 拆分。若存在，請你給出具體的拆分方案。
輸入
輸入只有一行，一個正整數 n，代表需要判斷的數。
輸出
如果這個數的所有拆分中，存在優(yōu)秀的拆分。那么，你需要從大到小輸出 這個拆分中的每一個數，相鄰兩個數之間用一個空格隔開?？梢宰C明，在規(guī)定 了拆分數字的順序后，該拆分方案是唯一的。 若不存在優(yōu)秀的拆分，輸出“-1”（不包含雙引號）。
提示
對于 20% 的數據，n ≤ 10。 對于另外 20% 的數據，保證 n 為奇數。
對于另外 20% 的數據，保證 n 為 2 的正整數次冪。
對于 80% 的數據，n ≤ 1024。
對于 100% 的數據，1 ≤ n ≤ 1 × 107。