3327.[NOIP1998 普及组] 幂次方

算法思路

1. 问题分析

本问题要求将正整数递归分解为2的幂次方的表示形式。核心挑战在于：

• 将数字分解为 $2^i$ 的线性组合
• 递归处理指数部分（当 $i>1$ 时）
• 规范处理边界情况（$i=0$ 和 $i=1$）

2. 解决策略

1. 递归分解：从最高幂次（$2^{14}$）开始向下枚举
2. 幂次处理：
   • $i=1$ 时直接输出 "2"
   • $i=0$ 时输出 "2(0)"
   • $i>1$ 时递归处理指数：输出"2(" → 递归处理i → 输出")"
3. 表达式拼接：每分解出一个幂次项后，若剩余值不为0，则添加 "+" 连接后续项

3. 复杂度分析

• 时间复杂度：$O((\log n)^2)$
  每次递归最多处理 $O(\log n)$ 个幂次项（15个），递归深度为 $O(\log n)$
• 空间复杂度：$O(\log n)$
  由递归调用栈深度决定（最大深度 $\log_2(20000) \approx 15$）

代码实现

C++解法

cpp
复制
1#include<iostream>
2#include<cmath>
3using namespace std;
4
5// 递归分解函数：将x表示为2的幂次方组合
6void fff(int x) {
7    // 从2<sup>14(16384)到2</sup>0(1)枚举可能的幂次
8    for (int i = 14; i >= 0; i--) {
9        int power_val = pow(2, i);  // O(1)计算幂值
10        
11        if (power_val <= x) {  // 找到当前可用的最大幂次
12            if (i == 1) {      // 特殊处理2^1
13                cout << "2";
14            } else if (i == 0) {  // 特殊处理2^0
15                cout << "2(0)";
16            } else {  // 递归处理指数部分
17                cout << "2(";
18                fff(i);        // 递归分解指数
19                cout << ")";
20            }
21            
22            x -= power_val;  // 减去已处理部分
23            if (x != 0) {    // 剩余部分非空时添加连接符
24                cout << "+";
25            }
26        }
27    }
28}
29
30int main() {
31    int n;
32    cin >> n;  // 读取输入值
33    fff(n);    // 开始递归分解
34    return 0;
35}

代码解释：

1. 函数参数：fff(int x) 处理整数x的分解
2. 核心逻辑：
   • 第8行：倒序枚举幂次（14→0），确保优先分解高次项
   • 第12-19行：三类情况的特殊处理（指数为1/0/其他）
   • 第22行：添加连接符的条件判断（剩余值非空）
3. 边界处理：
   • 指数0和1直接输出固定格式
   • 枚举范围上限14由数据范围 $n \leq 2 \times 10^4$ 确定（$2^{14}=16384$）

Python3解法

python
复制
1def fff(x):
2    # 从2<sup>14(16384)到2</sup>0(1)倒序枚举幂次
3    for i in range(14, -1, -1):  # O(15)循环
4        power_val = 2 ** i       # 计算幂值
5        
6        if power_val <= x:        # 找到当前可用最大幂次
7            if i == 1:            # 特殊处理2^1
8                print("2", end="")
9            elif i == 0:          # 特殊处理2^0
10                print("2(0)", end="")
11            else:                 # 递归处理指数部分
12                print("2(", end="")
13                fff(i)            # 递归分解指数
14                print(")", end="")
15            
16            x -= power_val        # 更新剩余值
17            if x != 0:             # 剩余部分非空时添加连接符
18                print("+", end="")
19
20def main():
21    import sys
22    n = int(sys.stdin.read())  # 读取输入值
23    fff(n)                    # 开始递归分解
24
25if __name__ == "__main__":
26    main()

代码解释：

1. 与C++差异：
   • 使用 range(14, -1, -1) 实现倒序枚举
   • end="" 参数避免换行输出
   • 幂计算用 ** 运算符替代 pow()
2. Python特性：
   • 动态类型：无需声明变量类型
   • 通过 sys.stdin.read() 读取单行输入
3. 关键逻辑：
   • 第3行：倒序枚举确保优先处理高次项
   • 第8行：递归调用处理指数部分
   • 第14行：连接符的条件判断逻辑

复杂度对比

选择建议：

1. 竞赛场景：优先选择C++实现，尤其对时间要求严格的题目
2. 快速原型：Python代码更简洁，适合验证算法逻辑
3. 数据规模：当 $n>10^6$ 时，C++的效率优势更明显

两种实现均通过样例验证（输入1315输出匹配），算法逻辑完全一致。Python实现避免了C++特有语法（如指针），符合题目要求。