2的幂次方表示

题目描述

任何一个正整数都能拆成 2 的幂之和。约定 $2^1$ 写作 2， $2^0$ 写作 2(0)， $2^k\ (k\ge 2)$ 写作 2(...) 且指数 $k$ 继续展开，项之间用 + 连接。如 $137=2^7+2^3+2^0$ 最终表示为 2(2(2)+2+2(0))+2(2+2(0))+2(0)。

输入：一个正整数 $n$ （ $n \le 20000$ ）。输出：一行， $n$ 的 0、2 表示，不含空格。

样例输入：

text

样例输出：

text

12(2(2)+2+2(0))+2(2+2(0))+2(0)

思路

取 $x$ 的最高位下标 $i=\lfloor\log_2 x\rfloor$ ，按 $i=0$ 、 $i=1$ 、 $i\ge 2$ 分别写出 2(0)、2、2(expand(i))，再对剩余 $x-2^i$ 递归并用 + 拼接。指数的展开规则与 $x$ 完全相同，同一个函数递归调用自身即可； $x=0$ 返回空串方便拼接。

参考代码

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#!/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-09-29 23:37
# update_at: 2026-09-29 23:37

import sys


def expand(x: int) -> str:
    """把 x 写成约定的 0/2 表示，例如 5 -> 2(2)+2(0)；x = 0 返回空串，方便递归拼接。"""
    if not x:
        return ''
    top = x.bit_length() - 1                    # 最高二进制位，即 x 中最大的那个 2 的幂的指数
    # 单个 2 的幂 2^top 的写法：指数 0 要显式写 2(0)，指数 1 按约定直接写 2，更大则递归展开指数
    head = '2(0)' if top == 0 else '2' if top == 1 else f'2({expand(top)})'
    tail = expand(x - (1 << top))               # 去掉最高位后剩下的数，例如 137 - 128 = 9
    return head + f'+{tail}' * bool(tail)


def solve() -> None:
    n = int(sys.stdin.buffer.read())
    print(expand(n))


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
40
41
42
43
44/**
 * 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-05 05:32
 * update_at: 2026-10-05 05:32
 */

#include <iostream>
#include <string>
using namespace std;

typedef long long ll;

// 把 x 展开成约定的 0、2 表示，例如 5 -> 2(2)+2(0)；x=0 返回空串，方便拼接余项
string expand(ll x) {
    if (x == 0) {
        return "";
    }
    ll top = 0; // top 是 x 的最高二进制位下标，即最大那个 2 的幂的指数
    while ((1LL << (top + 1)) <= x) {
        top++;
    }
    string head; // 单个 2^top 的写法
    if (top == 0) {
        head = "2(0)"; // 2^0 必须显式写成 2(0)
    } else if (top == 1) {
        head = "2"; // 2^1 约定直接写 2
    } else {
        head = "2(" + expand(top) + ")"; // 指数自身继续展开
    }
    string tail = expand(x - (1LL << top)); // 去掉最高位后的剩余部分
    if (tail != "") {
        return head + "+" + tail;
    }
    return head;
}

int main() {
    ll n;
    cin >> n;
    cout << expand(n) << endl;
    return 0;
}

目录

题目描述

思路

参考代码