优秀的拆分

题目描述

给定正整数 $n$ ，判断能否把它拆成若干个互不相同的 $2$ 的正整数次幂之和。若能，从大到小输出这些数；若不能，输出 -1。方案唯一。

输入为一行整数 $n$ ；输出为拆分数字空格分隔，或 -1。 $1\le n\le 10^7$ 。

思路

不同 2 的幂之和就是二进制展开，展开唯一。拆分合法当且仅当不需要 $2^0=1$ ，即 $n$ 为偶数。偶数时从高到低枚举第 $k\ge 1$ 位，若置位则输出 $2^k$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 14:11
# update_at: 2026-10-02 14:11

import sys


def split_powers(n: int) -> list[int]:
    """优秀的拆分：取 n 二进制中每个置位 k（k >= 1）对应的 2^k，按 k 从大到小排列。

    二进制展开是把正整数写成"不同 2 的幂之和"的唯一方式，所以拆分合法
    当且仅当展开里不需要 2^0，即 n 是偶数；此时直接删掉第 0 位就是答案。
    """
    if n & 1:  # 奇数必须用到 2^0 = 1，而 1 不是 2 的正整数次幂
        return []
    return [1 << k for k in range(n.bit_length() - 1, 0, -1) if n >> k & 1]


def solve() -> None:
    n = int(sys.stdin.buffer.read())
    powers = split_powers(n)
    print(' '.join(map(str, powers)) if powers else -1)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 16:14
 * update_at: 2026-10-06 16:14
 */
#include <iostream>
using namespace std;

typedef long long ll;

ll n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    // 奇数必用到 2^0 = 1，而 1 不是 2 的正整数次幂，无解
    if (n & 1) {
        cout << -1 << "\n";
        return 0;
    }

    // 偶数的二进制展开中第 0 位为 0，其余置位 k>=1 对应的 2^k 即答案
    bool first = true;
    for (ll k = 62; k >= 1; k--) {
        if (n >> k & 1) {
            if (!first) cout << " ";
            first = false;
            cout << (1LL << k);
        }
    }
    cout << "\n";

    return 0;
}

目录

题目描述

思路

参考代码