[NOIP 1998 普及组] 幂次方

题意

把正整数写成若干个 2 的幂之和，并按题目规定输出：

2^0 写成 2(0)；
2^1 写成 2；
2^k (k > 1) 写成 2(k 的同类表示)。

思路

任意正整数都可以按二进制拆成若干个 2^exponent。

从高位到低位扫描每个为 1 的二进制位：

指数为 0：输出 2(0)；
指数为 1：输出 2；
指数大于 1：输出 2(express(exponent))。

所有片段用 + 连接。

Python 知识

1 << power 表示 2^power。
number >> exponent & 1 判断某个二进制位是否为 1。
递归函数 express(number) 返回字符串，外层只负责 print。
先把片段放进 parts，最后 "+".join(parts)，避免处理最后一个加号。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21def express(number):
    parts = []
    power = 0

    while (1 << power) <= number:
        power += 1

    for exponent in range(power - 1, -1, -1):
        if number >> exponent & 1:
            if exponent == 0:
                parts.append("2(0)")
            elif exponent == 1:
                parts.append("2")
            else:
                parts.append(f"2({express(exponent)})")

    return "+".join(parts)


n = int(input())
print(express(n))

Guide 风格代码

cppbook《C++ 快速入门》教学风格的写法（std:: 前缀、i += 1 循环、0 起始下标）：

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
45
46
47/**
 * 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-08-14 14:55
 * update_at: 2026-08-14 14:55
 */
#include <iostream>

// 输出 n 的题目规定表示，例如 1315 输出 2(2(2+2(0))+2)+...
void decompose(int n) {
    if (n == 1) {
        std::cout << "2(0)";  // 2^0 写成 2(0)
        return;
    }
    if (n == 2) {
        std::cout << "2";  // 2^1 直接写成 2
        return;
    }
    // n <= 20000 < 2^15，所以只需要检查第 0 到第 14 位
    bool first = true;  // 第一个输出的项前面不需要加号
    for (int bit = 14; bit >= 0; bit -= 1) {
        if (((1 << bit) & n) == 0) {
            continue;  // 这一位是 0，不输出任何项
        }
        if (!first) {
            std::cout << "+";  // 后面的项之前都要补一个加号
        }
        first = false;
        if (bit == 0) {
            std::cout << "2(0)";
        } else if (bit == 1) {
            std::cout << "2";
        } else {
            std::cout << "2(";
            decompose(bit);  // 指数也要按同样的规则递归分解
            std::cout << ")";
        }
    }
}

int main() {
    int n;
    std::cin >> n;
    decompose(n);
    return 0;
}

复杂度

n <= 20000，二进制位数很小。时间复杂度约为 $O(\log n \log\log n)$ ，空间复杂度为递归深度 $O(\log n)$ 。

总结

这题的核心是把数字的二进制分解和题目的递归输出规则对齐。用列表收集片段可以让输出格式更稳。

[NOIP 1998 普及组] 幂次方

目录

题意

思路

Python 知识

代码

Guide 风格代码

复杂度

总结